Graph-based subcube allocation and task migration schemes for hypercube systems = 하이퍼큐브 시스템에서 그래프에 기초한 서브큐브 할당과 타스크 재배치에 관한 연구

For multi-user multi-tasking hypercube systems, there have been two fundamental problems in the processing of the incoming tasks: subcube allocation and task migration. In this thesis, we propose a new top-down subcube allocation scheme, called SIG (Subcube Information Graph) strategy, and also present a task migration scheme to solve the fragmentation problem in a hypercube. The SIG strategy is based on a heuristic and a undirected graph, called FC(Free Cube)-graph, whose vertices represent the available subcubes, and edges response time and internal/external fragmentation, and to generate the higher dimension subcube by the cycle detection in the FC-graph. When a subcube is released, a heuristic algorithm is also used to maintain the available subcubes as large as possible and to reduce the response time. To effectively utilize non-cubic topology on hypercubes, the SIG strategy is extended to support non-cubic allocation. Using the connectivity information among free subcubes in the FC-graph, the SIG strategy utilizes smaller subcubes which are physically adjacent to each other for non-cubic allocation.
Advisors
Cho, Jung-Wanresearcher조정완researcher
Publisher
한국과학기술원
Issue Date
1992
Identifier
60519/325007 / 000825005
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학과, 1992.8, [ v, 100 p. ]

URI
http://hdl.handle.net/10203/32933
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=60519&flag=t
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 122
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0