오류가 있는 메쉬 시스템에서의 프로세서 할당 기법

서경희,Seo, Kyung-Hee 한국정보처리학회 2005 정보처리학회논문지 A Vol.12 No.4

오류가 발생할 수 있는 대규모 멀티컴퓨터 시스템의 프로세싱 자원들을 효율적으로 사용하기 위해서는 신뢰도 높은 프로세서 할당 알고리즘이 요구된다. 본 논문에서는 오류가 있는 메쉬 시스템의 성능을 높일 수 있는 동적이면서 신뢰도 높은 프로세서 할당 기법을 제안한다. 비경계 오류 노드들을 보상할 수 있는 오류프리 상한 또는 하한 경계 노드들을 사용해서 오류가 있는 메쉬 시스템을 최대 볼록 시스템으로 재구성한다. 이 재구성된 비직사각형 메쉬 시스템을 효율적으로 활용하기 위해 기존의 사각형 서브메쉬를 할당 할 수 없을 때 L-모양 서브메쉬를 할당할 수 있다. 시뮬레이션 결과를 통해서 제안하는 기법이 작업응답시간과 시스템 활용도 면에서 다른 기법들보다 우수함을 보인다. Efficient utilization of processing resources in a large multicomputer system with the possibility of fault occurrence depends on the reliable processor management scheme. This paper presents a dynamic and reliable processor allocation strategy to increase the performance of mesh-connected parallel systems with faulty processors The basic idea is to reconfigure a faulty mesh system into a maximum convex system using the fault-free upper or lower boundary nodes to compensate for the non-boundary faulty nodes. To utilize the non-rectangular shaped system parts, our strategy tries to allocate L-shaped submeshes instead of signaling the allocation failure. Extensive simulations show that the strategy performs more efficiently than other strategies in terms of the job response time md the system utilization.

연속적인 서브메쉬 할당기법에서 단편화를 최소화하는 기법

서경희,김성천,Seo Kyung Hee,Kim Sung Chun 한국정보처리학회 2005 정보처리학회논문지 A Vol.12 No.2

대규모 멀티컴퓨터 시스템에서 단편화를 줄일 수 있는 적응성 있는 프로세서 할당 기법을 제안한다. 큰 크기의 서브메쉬 할당을 요구하는 작업들의 개수가 적을 경우에도 나머지 작업들의 대기 큐의 지연시간이 증가할 수 있다. 이런 상황에서 할당이 불가능한 기존의 기법들과 달리, L-모양 서브메쉬를 할당할 수 있으며, 할당 가능한 L-모양 서브메쉬를 효율적으로 탐색하는 알고리즘을 개발하였다. 그러므로 FCFS로 스케쥴링되어도, 대기 큐의 지연시간을 줄임으로써 평균응답시간을 줄일 수 있다. 시뮬레이션 결과를 통해서 제안하는 기법이 외부 단편화, 작업응답시간, 그리고 시스템의 활용도 면에서 다른 기법들보다 우수함을 보인다. This paper presents an adaptive processor allocation strategy to reduce fragmentation in a large multi-user multicomputer system. A small number of jobs with unexpectedly large submesh allocation requirements may significantly increase the queuing delay of the rest of jobs. Under such circumstances, our strategy further tries to allocate L-shaped submeshes instead of signaling the allocation failure unlike other strategies. We have developed the efficient algorithm to find the allocatable L-shaped submeshes. Thus, our strategy reduces the mean response time by minimizing the queuing delay, even though jobs are scheduled in an FCFS to preserve fairness. The simulations show that our strategy performs more efficiently than other strategies in terms of the job response time and the system utilization.

이기종 멀티프로세서 시스템에서 삽입과 복제를 고려한 효율적인 태스크 스케줄링 알고리즘

윤완오(WanOh Yoon),송인성(InSeong Song),이창호(ChangHo Lee),최상방(SangBang Choi) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.2

이기종 멀티프로세서 시스템 환경에서 방향성 비순환 그래프(DAG)의 각 태스크를 효율적으로 스케줄링 하는 것은 전체 시스템의 성능을 향상시키는데 매우 중요한 역할을 한다. 이기종 멀티프로세서 시스템 환경에서 입력 DAG로 표현되는 병렬 응용프로그램을 스케줄링 하기 위한 최적의 방법을 찾는 것은 ‘NP-complete’ 문제로, 최적에 가까운 스케줄링 결과 값을 얻기 위해서는 휴리스틱 방법으로 접근해야 한다. 본 논문에서는 프로세서선택 과정에서 각 태스크의 삽입과 복제 여부를 함께 고려하여 최적의 프로세서를 선택함으로써 전체적인 성능을 향상시키는 HMPID 알고리즘을 제안한다. 제안하는 알고리즘의 성능 분석을 위해 많은 수의 입력 그래프를 생성하여 삽입 또는 복제의 방법을 사용하는 기존의 대표적인 태스크 스케줄링 알고리즘인 HCPFD, DCPD, HEFT와 비교하였다. 비교 실험 결과 본 논문에서 제안하는 HMPID 알고리즘이 기존의 알고리즘에 비해 뛰어난 성능을 보이는 것을 확인하였다. In heterogeneous multi-processor system, efficient scheduling of tasks in DAG is a key to improve the performance of the system. Finding the best optimal scheduling method of parallel application which is modeled as an input DAG, is an NP-complete problem. So, heuristic method has to be used to find the sub-optimal method. In this paper, we propose a HMPID algorithm which considers both insertion and duplication in processor selection phase. To analyze the performance of the proposed algorithm, we generated various input graphs and compared the results with HCPFD, DCPD, HEFT, the most popular conventional task scheduling algorithms. The results show that HMPID algorithm provides superior performance than other conventional algorithms.

16비트 명령어 기반 프로세서를 위한 페어 레지스터 할당 알고리즘

이호균,김선욱,한영선,Lee, Ho-Kyoon,Kim, Seon-Wook,Han, Young-Sun 한국정보처리학회 2011 정보처리학회논문지 A Vol.18 No.6

다양한 영역에서32비트 명령어 기반 마이크로프로세서의 사용이 일반화되고 있지만, 임베디드 시스템 환경에서는 여전히 16비트 명령어 기반 프로세서가 널리 사용되고 있다. 인텔 8086, 80286 및 모토로라 68000, 그리고 에이디칩스의 AE32000과 같은 프로세서들이 그 대표적인 예이다. 그러나, 16비트 명령어들은 32비트 명령어보다 그 크기로 인해 상대적으로 낮은 표현력을 가지고 있어 동일한 기능을 구현하는데 32비트 명령어 기반 프로세서에 비해 많은 명령어를 수행해야 한다는 문제점을 가지고 있다. 실행 명령어 수는 프로세서의 실행 성능과 밀접한 관련을 가지므로 16비트 명령어셋의 표현력을 향상시켜 성능 저하 문제를 해결할 필요성이 있다. 본 논문에서는 기존의 그래프 컬러링 기반 레지스터 할당(Graph-coloring based Register Allocation) 알고리즘을 보완한 페어 레지스터 할당(Pair Register Allocation) 알고리즘을 제안하고, 이를 통한 성능 분석 결과 및 추후 연구 방향을 제시하고자 한다. Even though 32-bit ISA based microprocessors are widely used more and more, 16-bit ISA based processors are still being frequently employed for embedded systems. Intel 8086, 80286, Motorola 68000, and ADChips AE32000 are the representatives of the 16-bit ISA based processors. However, due to less expressiveness of the 16-bit ISA from its narrow bit width, we need to execute more 16-bit instructions for the same implementation compared to 32-bit instructions. Because the number of executed instructions is a very important factor in performance, we have to resolve the problem by improving the expressiveness of the 16-bit ISA. In this paper, we propose a new pair register allocation algorithm to enhance an original graph-coloring based register allocation algorithm. Also, we explain about both the performance result and further research directions.

DSP용 코드 생성에서 주소 포인터 할당 성능 향상 기법

이희진(Heejin Lee),이종열(Jong-Yeol Lee) 대한전자공학회 2008 電子工學會論文誌-CI (Computer and Information) Vol.45 No.1

DSP에서 제공되는 주소 생성 유닛은 데이터 패스와 병렬적으로 주소 연산을 수행할 수 있게 해 줌으로써, DSP 코드 생성에 중요한 역할을 한다. 프로그램 변수들의 메모리 레이아웃을 결정하는 문제는 주소 생성 유닛의 기능을 이용하여 주소 연산용 명령어를 줄이는 최적화이다. 메모리 레이아웃 생성 단계와 주소 포인터 할당 단계로 구분 되는 이 최적화에서 본 논문은 주소 연산 코드의 수가 최소가 되도록 DSP용 코드 생성의 효과적인 주소 포인터 할당 문제를 다룬다. 제안하는 알고리즘은 고정된 메모리 레이아웃을 가질 때 주소 포인터 할당을 수행하는 기존의 알고리즘의 시간 복잡도를 줄이는 기법이다. 메모리크기와 수행 시간을 줄이기 위해 알고리즘을 수행할 때 핵심적인 요소들만을 고려하도록 강한 가지치기 방법을 사용하였다. 또한 주소 포인터 할당 문제는 메모리 레이아웃에 영향을 크게 받는 문제이기 때문에 본 논문은 주어진 메모리 레이아웃을 갱신하여 반복적으로 성능을 개선하는 방법을 제안한다. 약 3,000여개의 실제 프로그램으로부터 얻은 변수 접근 시퀀스를 제공하는 OffsetStone 벤치마크를 이용한 실험결과를 통해 본 논문에서 제안한 기법과 알고리즘을 테스트 했다. 제안한 방법은 전통적인 방법보다 평균 25.9%의 적은 주소 코드를 생성해 냄을 보인다. Exploitation of address generation units which are typically provided in DSPs plays an important role in DSP code generation since that perform fast address computation in parallel to the central data path. Offset assignment is optimization of memory layout for program variables by taking advantage of the capabilities of address generation units, consists of memory layout generation and address pointer assignment steps. In this paper, we propose an effective address pointer assignment method to minimize the number of address calculation instructions in DSP code generation. The proposed approach reduces the time complexity of a conventional address pointer assignment algorithm with fixed memory layouts by using minimum cost-nodes breaking. In order to contract memory size and processing time, we employ a powerful pruning technique. Moreover our proposed approach improves the initial solution iteratively by changing the memory layout for each iteration because the memory layout affects the result of the address pointer assignment algorithm. We applied the proposed approach to about 3,000 sequences of the OffsetStone benchmarks to demonstrate the effectiveness of the our approach. Experimental results with benchmarks show an average improvement of 25.9% in the address codes over previous works.

하이퍼큐브에서의 효과적인 프로세서할당 기법

손유익(Son Yoo Ek),남재열(Nam Jae Yeal) 한국정보처리학회 1996 정보처리학회논문지 Vol.3 No.4

Processors must be allocated to incoming tasks in a way that will maximize the processor utilization and minimize the system fragmentation. Thus, an efficient method of allocating processors in a hypercube is o key to system performance. In order to achive this goal, it is necessary to detect the availability of a subcube of required size and merge the released small cubes to form a lager ones. This paper presents the tree-exchange algorithm which determines the levels and parters of the binary tree representation of a hypercube, and an efficient allocation strategy using the algorithm. The complexity for search time of the algorithm is O[n/2]*2n and it shows good performance in comparison with other strategies.

Theoretical Performance Bounds and Parallelization of a Two-Dimensional Packing Algorithm

황인재,홍동권,Hwang, In-Jae,Hong, Dong-Kweon Korea Information Processing Society 2003 정보처리학회논문지 A Vol.10 No.1

이차원 팩킹 알고리즘은 메쉬 멀티프로세서 시스템을 분할 및 할당하는데 유용하게 활용될 수 있다. 기존연구에서 TP 휴리스틱 알고리즘이라 불리는 효율적인 팩킹 알고리즘을 개발하였으며 팩킹 결과가 어떻게 메쉬 멀티프로세서 시스템을 분할 및 할당하는데 활용될 수 있는지 보여주었다. 본 논문에서는 TP 휴리스틱 알고리즘의 이론적인 성능분석결과를 제시한다. 또한 알고리즘을 병렬화하여 다수의 프로세서를 이용하여 수행되었을 때 보다 적은 수행시간을 소모하게 한다. Two-dimensional packing algorithm can be used for allocating submeshes in mesh multiprocessor systems. Previously, we developed an efficient packing algorithm called TP heuristic, and showed how the results of the packing could be used for allocating submeshes. In this paper, we present theoretical performance bounds for TP heuristic. We also present a parallel version of the algorithm that consumes reduced time when it is executed by multiple processors in mesh multiprocessors.

분산 이기종 시스템에서 리스트 스케줄링 알고리즘을 위한 새로운 프로세서 할당 정책

윤완오(Wan-Oh Yoon),송인성(In-Seong Song),윤준철(Jun-Chol Yoon),최상방(Sang-Bang Choi) 한국정보과학회 2010 정보과학회논문지 : 시스템 및 이론 Vol.37 No.2

분산 이기종 시스템의 성능은 DAG로 주어지는 입력 그래프를 스케줄링 하는 알고리즘의 성능에 좌우된다. 많은 스케줄링 알고리즘 중에 리스트 스케줄링 알고리즘은 낮은 복잡도를 가지면서 우수한 성능을 보이고 있다. 리스트 스케줄링은 태스크 우선순위 결정 단계와 프로세서 할당 단계로 이루어져 있으나 대부분의 연구들은 태스크 우선순위 결정 단계만을 연구하고 있다. 본 논문에서는 기존의 할당 정책과 동일한 복잡도를 가지면서 성능이 향상된 새로운 프로세서 할당 정책인 LIP 정책을 제안한다. 기존의 리스트 스케줄링 알고리즘인 HEFT, HCPT, GCA, PETS의 태스크 우선순위 결정 정책에 본 논문에서 제안한 LIP 정책을 적용하여 실험한 결과 기존의 프로세서 할당 정책인 삽입 정책과 비 삽입 정책보다 성능 향상이 있는 것을 확인할 수 있었다. The performance of Distributed Heterogeneous Computing System depends on the algorithm which schedules input DAG graph. Among various scheduling algorithms, list scheduling algorithm provides superior performance with low complexity. List scheduling consists of task prioritizing phase and processor allocation phase, but most studies only focus on task prioritizing phase. In this paper, we propose LIP policy which has the same complexity with traditional allocation policies but has superior performance. The performance of LIP has been observed by applying them to task prioritizing phase of traditional list scheduling algorithms, HCPT, HEFT, GCA, and PETS. The results show that LIP has better performance than insertion-based policy and non-insertion-based policy, which are traditional processor allocation policies.