Title :
VLSI routing on the pipelined hypercube and related networks
Author_Institution :
Dept. of Electr. Eng., Maryland Univ., College Park, MD, USA
Abstract :
The author presents parallel algorithms for several important combinatorial problems related to VLSI routing. These algorithms achieve linear speed-ups on the pipelined hypercube, and provably optimal speed-ups on the shuffle-exchange and the cube-connected-cycles, for any number p of processors satisfying 1 ⩽ p ⩽ n/log3n (log logn)2, where n is the input size. The lower bound results are established under no restriction on how the input is mapped into the local memories of the different processors
Keywords :
VLSI; circuit layout CAD; combinatorial mathematics; hypercube networks; multiprocessor interconnection networks; network topology; parallel algorithms; IC layout design; VLSI routing; combinatorial problems; cube-connected-cycles; parallel algorithms; pipelined hypercube; shuffle-exchange; Communication switching; Computer networks; Concurrent computing; Educational institutions; Hypercubes; Packet switching; Parallel algorithms; Routing; Switches; Very large scale integration;
Conference_Titel :
VLSI, 1991. Proceedings., First Great Lakes Symposium on
Conference_Location :
Kalamazoo, MI
Print_ISBN :
0-8186-2170-2
DOI :
10.1109/GLSV.1991.143933
