Simulated annealing approach to task allocation problem in hypercube = 하이퍼큐브 컴퓨터에서 시뮬레이티드 어닐링에 의한 일의 할당에 관한 연구

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 173
  • Download : 0
This thesis deals with the simulated annealing approach to task allocation problem in parallel computing system, sepecially in hypercube. Simulated annealing has been given much attention for its insensitivity to the problem in concern, its capability to adapt any complex objective functions and constraints, its simplicity to implement any kinds of problem, and its performance to find "good" solutions, compared to other combinatorial optimization methods. On the contrary it needs very large computational efforts and this shortcoming makes it intractable to use simulated annealing to solve task allocation problem. We found, however, that task allocation problem has some peculiar characteristics which cannot be met in other combinatorial problems. This thesis points out such characteristics and, by utilizing them to the best, attempts to make simulated annealing be tractable one for solving task allocation problem in computational time. We show that the size of the configuration space for task allocation problem can be reduced in great extent. New algorithms for generating set of moves are preposed. By using these algorithms, the efficiency of simulated annealing algorithm is ever increased and hence less computation time is required. We empirically show that no serious local optima are exist in the task allocation problem if the target processor architecture has degree of regularity and symmetry, which are quite realistic assumptions for today``s most existing parallel compution systems, and by using this fact an argument for setting the initial value of temperature paramenter is described. In the second part of the thesis, we present another view point of simulated annealing; while most provious works on simulated annealing have focused on th "optimization" aspect of annealing, we pay much attention to the "simulation" aspect of it. By changing the view point of simulated annealing in this way, more efficient annealing schedules can be developed with the aids o...
Advisors
Kim, Myung-Hwanresearcher김명환researcher
Description
한국과학기술원 : 전기 및 전자공학과,
Publisher
한국과학기술원
Issue Date
1991
Identifier
61725/325007 / 000855225
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전기 및 전자공학과, 1991.2, [ vii, 86 p. ]

URI
http://hdl.handle.net/10203/36157
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=61725&flag=dissertation
Appears in Collection
EE-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0