연속적인 서브메쉬 할당기법에서 단편화를 최소화하는 기법
Minimizing Fragmentation in Contiguous Submesh Allocation Scheme
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
대규모 멀티컴퓨터 시스템에서 단편화를 줄일 수 있는 적응성 있는 프로세서 할당 기법을 제안한다. 큰 크기의 서브메쉬 할당을 요구하는 작업들의 개수가 적을 경우에도 나머지 작업들의 대기 큐의 지연시간이 증가될 수 있다. 이런 상황에서 할당이 불가능한 기존의 기법들과 달리, L-모양 서브메쉬를 할당할 수 있으며, 할당 가능한 L-모양 서브메쉬를 효율적으로 탐색하는 알고리즘을 개발하였다. 그러므로 FCFS로 스케쥴링되어도, 대기 큐의 지연시간을 줄임으로써 평균응답시간을 줄일 수 있다. 시뮬레이션 결과를 통해서 제안하는 기법이 외부 단편화, 작업응답시간, 그리고 시스템의 활용도 면에서 다른 기법들보다 우수함을 보인다.
Abstract
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
참고문헌 (19)
- A. Alan, "Simulation with Visual SLAM and AweSim" (1997), John Wiley & Sons, Inc.
- D. Babbar, "A performance Comparison of Processor Allocation and Job Scheduling Algorithms for Mesh-Connected Multiprocessors", pp.46~53 (1994)
- C. Chang, "An Integrated Processor Management Scheme for the Mesh-Connected Multi- computer Systems", pp.118~121 (1997)
- P. J. Chuang, "An Efficient Submesh Allocation Strategy for Mesh Computer systems", pp.256~263 (1991)
- J. Ding, "An Adaptive Submesh Allocation Strategy for Two-Dimensional Mesh Connected systems", ii, pp.193~200 (1993)
- V. Gupta, "A Flexible Processor Allocation Strategy For Mesh Connected Parallel Systems", III, pp.166~173 (1996)
- K. Hwang, "Scalable Parallel Computing: Technology, Architecture, Programming", pp.280~ (1998), WCB[DOI]
- J. W. Hong, "Cost Trade-offs in Graph Embeddings, with Applications", 30(4), pp.709~728 (1983)
- M. Kang, "Isomorphic Strategy for Processor Allocation in k-Ary n-Cube Systems", 52(5), pp.645~657 (2003)
- K. Li, "A Two-Dimensional Buddy System for Dynamic Resource Allocation in a Parti- tionable Mesh Connected System", pp.22~28 (1990)
- T. Liu, "A Submesh Allocation Scheme for Mesh- Connected Multiprocessor Systems", ii, pp.159~163 (1995)
- W. Liu, "Non-contiguous Processor Allocation Algorithms for Distributed Memory Multicomputers", pp.227~236 (1994)
- K.H. Seo, "Improving system performance in contiguous processor allocation for mesh-connected parallel systems", 67(Issue 1), pp.45~54
- D. D. Sharma, "A Fast and Efficient Strategy for Submesh Allocation in Mesh-Connected Parallel Computers", pp.682~689
- D. D. Sharma, "Job Scheduling in Mesh Multicomputers", ii, pp.251~258 (1994)
- X. Shen, "On Embedding Between 2D Meshes of the Same Size", 46(8), pp.880~889 (1997)
- K. Windisch, "Contiguous and Non- Contiguous Processor Allocation Algorithms For K-ary and N-cubes", ii, pp.164~168 (1995)
- B. S. Yoo, "A Fast and Efficient Processor Allocation Scheme for Mesh-Connencted Multicomputers", 51(1), pp.46~60 (2002)
- Y. Zhu, "Efficient Processor Allocation Strategies for Mesh-Connected Parallel Computers", 16(12), pp.328~337