병렬 처리장치의 개수에 따른 스케줄링 알고리즘의 제안 및 성능평가

박경린 ( Gyung-leen Park ),이상준 ( Sang Joon Lee ),이봉규 ( Bongkyu Lee ) 한국인터넷정보학회 2000 인터넷정보학회논문지 Vol.1 No.2

병렬처리 시스템에서의 스케줄링 문제는 응용 프로그램의 병렬 수행 시간을 최소화하는 스케줄을 찾아내는 문제로 지난 수 십년 간 중요한 연구 과제였으며 복제 기반 스케줄링 알고리즘들은 이 문제를 해결하기 위해 제안된 비교적 새로운 접근 방법이다 복제 기반 스케줄링 알고리즘들은 작업들을 복제함으로써 작업들간의 통신비용을 줄이는 방법으로 대부분의 복제 기반 스케줄링 알고리즘들은 무한한 수의 처리장치의 존재를 가정한다 이러한 가정은 현실적이지 못하므로 본 논문은 사용 가능한 처리장치의 수에 따라 다른 스케줄을 생성하는 스케줄링 알고리즘을 제안하고 그 성능을 평가한다 성능 평가 결과는 작업의 수가 N일 경우에 처리장치의 수가 N개 이상이면 무한한 처리장치의 수를 가정하였을 경우와 같은 스케줄을 생성하고 사용 가능한 처리장치의 수가 N개 이하로 감소함에 따라 병렬 수행 시간이 서서히 증가함을 보인다 The scheduling problem in parallel processing systems has been a challenging research issue for decades. The problem is defined as finding an optimal schedule which minimizes the parallel execution time of an application on a target multiprocessor system. Duplication Based Scheduling (DBS) is a relatively new approach for solving the problem, The DBS algorithms are capable of reducing communication overhead by duplicating remote parent tasks on local processors. Most of DBS algorithms assume an availability of the unlimited number of processors in the system. Since the assumption may not hold in practice, the paper proposes a new scalable DBS algorithm for a target system with limited number of processors. It is shown that the proposed algorithm with N available processors generates the same schedule as that obtained by the algorithm with unlimited number of processors, where N is the number of input tasks. Also, the performance evaluation reveals that the proposed algorithm shows a graceful performance degradation as the number of available processors in the system is decreased.

병렬 처리 시스템을 위한 효율적인 복제 중심 스케줄링 알고리즘

박경린(Park Gyung Leen),추현승(Choo Hyun Seung) 한국정보처리학회 1999 정보처리학회논문지 Vol.6 No.8

Multiprocessor scheduling problem has been an important research area for the past decades. The problem is defined as finding an optimal schedule which minimizes the parallel execution time of an application on a target multiprocessor system. Duplication Based Scheduling (DBS) is a relatively new approach for solving multiprocessor scheduling problems. This paper classifies DBS algorithms into two categories according to the task duplication method used. The paper then presents a new DBS algorithm that extracts the strong features of the two categories of DBS algorithms. The simulation study shows that the proposed algorithm achieves considerable performance improvement over existing DBS algorithms with similar time complexity.

다중 처리기 시스템을 위한 효율적인 리스트 스케줄링 알고리즘

박경린(Gyung Leen Park),추현승(Hyun Seung Choo),이정훈(Jeong Hoon Lee) 한국정보처리학회 2000 정보처리학회논문지 Vol.7 No.7

Scheduling parallel tasks, represented as a Directed Acyclic Graph (DAG) or task graph, on a multiprocessor system has been an important research area in the past decades. List scheduling has been a typical approach for solving the problem. List scheduling algorithms assign priorities to a node or an edge in an input DAG, and then generate a schedule according to the assigned priorities. This paper proposes a list scheduling algorithm with effective method of priority assignments. The paper also analyzes the worst case performance and optimality condition for the proposed algorithm. The performance comparison study shows that the proposed algorithm outperforms existing scheduling algorithms especially for input DAGs with high communication overheads. The performance improvement over existing algorithms becomes larger as the input DAG becomes more dense and the level of parallelism in the DAG is increased.

텔레매틱스 기반 컨버전스 서비스 및 기술 동향

박경린(Gyung-Leen Park),이정훈(Junghoon Lee),신인혜(In-Hye Shin) 한국정보과학회 2008 정보과학회지 Vol.26 No.1

심야 주차공간 할당을 위한 수요 매칭 서비스의 설계

이정훈(Lee, Jung Hoon),박경린(Park, Gyung Leen) 대한공간정보학회 2021 대한공간정보학회지 Vol.29 No.4

본 논문은 스마트 시티에서 심야 주차공간을 효율적으로 수요자에게 할당하면서 공급자에게는 주차공간 제공에 의한 수입을 향상시킬 수 있는 수요-공급 매칭 서비스를 설계하고 모의실험에 의해 그 성능을 평가한다. 매칭 서비스는 정해진 싯점마다 주기적으로 수행되며 수요자와 공급자(주자창 제공자)는 그 시간 전까지 자신의 요구사항을 등록한다. 이때, 수요자는 선호도 순서대로 (원하는 주차공간, 비딩 레벨) 쌍을 지정하는 반면, 공급자는 가격, 거리 등 자신의 선택 기준을 명세한다. 매칭 엔티티의 수를 n이라고 할 때 제안하는 기법은 n²에 비례하는 시간 내에 매칭을 수행할 수 있어서 수만대의 주차 요구를 수용할 수 있다. 모의실험 결과, 제안된 기법은 일반적인 선입선출방식에 비해 주차공간 제공자의 수입을 26.0 %p까지 향상시키면서 주차공간까지의 거리를 31 %p까지 줄인다. This paper designs an efficient demand-supply matching scheme for overnight parking and evaluates its performance via simulation. After collecting the preference lists specifying desired parking spots and associated bidding levels from demanders, this service allocates the parking space based on the pre-registered priority function of each space provider, by means of the customized stable marriage problem solver. The execution time time complexity is O(n²), where n is the number of matching entities. The simulation results show that the proposed scheme cannot only reduce the distance to the parking space by up to 31.0 %p but also enhances the parking revenue of space providers by up to 26.0 %p for the given parameter setting.

3차원 토러스 구조를 갖는 멀티컴퓨터에서의 동적 작업 스케줄링 알고리즘

추현승,윤희용,박경린,Choo, Hyun-Seung,Youn, Hee-Yong,Park, Gyung-Leen 한국정보처리학회 2001 정보처리학회논문지 A Vol.8 No.3

멀티컴퓨터 시스템은 많은 연산 노드들을 이용함으로써 높은 성능을 얻는다. 다차원 매쉬(mash)는 단순함과 효율성 때문에 멀티컴퓨터 구조로 널리 이용되었다. 본 논문은 3차원 토러스(torus) 시스템을 위한 최초 적합(first-fit) 방법에 기반한 효율적인 프로세서 할당 알고리즘을 제안한다. 이 알고리즘은 CST(Coverage Status Table)을 이용하여 3차원 정보를 2차원 정보로 변형하므로써 프로세서 할당 시간을 최소화 한다. 종합적인 컴퓨터 시뮬레이션 결과는 제안한 방법이 최적 적합(best-fit)에 기반한 기존 방법들과 비교해서 프로세서 이용률은 비슷하면서, 프로세서 할당 시간이 항상 짧다는 것을 보여준다. 성능 차이는 입력 부하가 증가함에 따라 더욱 두드러진다. 다른 스케줄링 환경상에서 제안된 방법의 성능을 조사하기 위해서, 전형적인 FCFS 스케줄링 기법과 함께 non-FCFS 스케줄링 기법도 연구된다. Multicomputer systems achieve high performance by utilizing a number of computing nodes. Multidimensional meshes have become popular as multicomputer architectures due to their simplicity and efficiency. In this paper we propose an efficient processor allocation scheme for 3D torus based on first-fit approach. The scheme minimizes the allocation time by effectively manipulating the 3D information an 2D information using CST (Coverage Status Table). Comprehensive computer simulation reveals that the allocation time of the proposed scheme is always smaller than the earlier scheme based on best-fit approach, while allowing comparable processor utilization. The difference gets more significant as the input load increases. To investigate the performance of the proposed scheme with different scheduling environment, non-FCFs scheduling policy along with the typical FCFS policy is also studied.

유전자 알고리즘에 기반한 이동식 주차단속 차량의 운행 스케줄 결정

이정훈(Lee, Jung Hoon),박경린(Park, Gyung Leen) 대한공간정보학회 2021 대한공간정보학회지 Vol.29 No.2

이차원 메쉬 상호 연결 망에 대한 효율적인 태스크할당 알고리즘

추현승(Choo Hyun Seung),박경린(Park Gyung Leen),유성무(Yoo Seong Moo) 한국정보처리학회 1999 정보처리학회논문지 Vol.6 No.6

An effective allocation of requested number of processors to newly incoming tasks in two-dimensional (2D) mesh interconnection networks is very important for achieving the desired high performance and resource utilization. It also needs to guarantee the complete recognition of the free submeshes based on contiguous and available processors with minimum overhead. An efficient task allocation algorithm for 2D meshes is presented in this paper. By employing a new approach for searching the one-dimensional array, the proposed algorithm can find the available submesh without the scanning of the entire 2D array unlike earlier designs. As a result, the new algorithm can significantly reduce the task allocation time. Comprehensive computer simulation shows that the average allocation time and waiting delay are much smaller than earlier designs irrespective of the size of meshes. The hardware overhead is comparable to other algorithms.

위치이력 데이터를 이용한 공택시 배치에 관한 연구

이정훈(Junghoon Lee),박경린(Gyung-Leen Park) 대한공간정보학회 2008 한국지형공간정보학회 학술대회 Vol.2008 No.10

본 논문은 택시들의 승차율을 높이고 승객들의 대기시간을 최소화하기 위하여 제주 택시들의 이동이력 데이터를 기반으로 하여 공차들을 승객을 만날 가능성이 많은 지역으로 배치하는 기법을 제시한다. 이동이력 데이터에 포함된 공차 보고와 승차 보고 수 사이의 스케일 차이를 극복하기 위하여 전체수와 영역내 합에 대한 비율로 정규화하는 방법을 설명하고 장단점을 분석한다. 또 시간대별, 요일별, 주간별 택시들의 승객 대기시간에 대한 통계 데이터에 기반하여 가장 수요와 공급이 적정하게 유지되는 시간구간을 발견하고 이 구간에 대한 택시 분포와 현재의 택시 분포의 차이에 의해 수요보다 공급이 많은 곳의 택시를 재배치한다.

출구 버퍼모듈을 갖는 패킷교환식 상호 연결 망의 성능 분석

추현승(Choo Hyun Seung),박경린(Park Gyung Leen) 한국정보처리학회 1999 정보처리학회논문지 Vol.6 No.4

Packet-switched multistage interconnection networks(MINs) have been widely used for digital switching systems and super computers. In this paper we show that multiple packets in a switching element can move to the succeeding switching element in one network cycle by fully utilizing the cycle bandwidth. Only one packet movement was usually assumed in typical MINs. We present an analytical model for the MINs with the multiple packet movement scheme, and validate it by computer simulation. Comparisons with the traditional MINs of single packet movement reveal that the throughput is increased up to about 30% for practical size MINs. Similar result was also obtained for delays. The performance increase is more significant when the network traffic is nonuniform.