Title :
Heuristic technique for processor and link assignment in multicomputers
Author :
Bollinger, S. Wayne ; Midkiff, Scott F.
Author_Institution :
Bradley Dept. of Electr. Eng., Virginia Polytech. Inst. & State Univ., Blacksburg, VA, USA
fDate :
3/1/1991 12:00:00 AM
Abstract :
A graph-based solution to the mapping problem using the simulated annealing optimization heuristic is developed. An automated two-phase mapping strategy is formulated: process annealing assigns parallel processes to processing nodes, and connection annealing schedules traffic connections on network data links so that interprocess communication conflicts are minimized. To evaluate the quality of generated mappings. cost functions suitable for simulated annealing that accurately quantify communications overhead are derived. Communication efficiency is formulated to measure the quality of assignments when the optimal mapping is unknown. The mapping scheme is implemented using the hypercube as a host architecture, and results for several image graphs are presented
Keywords :
graph theory; hypercube networks; simulated annealing; automated two-phase mapping; communication conflicts; communication efficiency; communications overhead; connection annealing; cost functions; hypercube architecture; image graphs; link assignment; mapping problem; multicomputers; network data links; parallel processes; process annealing; processing nodes; processor assignment; scheduling; simulated annealing optimization heuristic; traffic connections; Algorithm design and analysis; Computer architecture; Hypercubes; Parallel algorithms; Processor scheduling; Simulated annealing; System performance; Telecommunication traffic; Topology; Traffic control;
Journal_Title :
Computers, IEEE Transactions on
