DESIGN OF A PARALLEL CAD SYSTEM

WE PROPOSE TO STUDY AND EVALUATE ALGORITHMS WHICH ARE APPROPRIATE TO TWO NUMERICALLY INTENSIVE PARTS OF ELECTRICAL CAD SYSTEMS, VIA. COMPONENT PLACEMENT AND CIRCUIT ROUTING. BOTH PROBLEMS ARE EXTREMELY COMPUTATIONALLY INTENSIVE OFTEN REQUIRING TIMES OF THE ORDER OF HOURS ON SEQUENTIAL MACHINES. THE NEED IS FOR TURNAROUND TIMES ON THE ORDER OF MINUTES AND PARALLEL PROCESSING IS A NATURAL WAY TO GAIN THE REQUIRED SPEEDUPS. IN THE ROUTING AREA WE INTEND TO EXAMINE ALGORITHMS IN USE OF SEQUENTIAL MACHINES AND THEIR APPLICABILITY TO PARALLEL COMPUTERS AS WELL AS DEVELOPING NEWER ALGORITHMS DERIVED FROM GRAPH THEORETICAL CALCULATIONS WHICH MAY HAVE BETTER PARALLELISM.THE COMPONENT PLACEMENT PROBLEM WILL BE STUDIED ON THE BASIS OF APPLYING MONTE CARLO TECHNIQUES WHICH ARE KNOWN TO HAVE GOOD PARALLEL EFFICIENCIES. WE WILL ATTEMPT TO DERIVE A MONTE CARLO PROCEDURE THAT LINKS THE PLACEMENT AND ROUTING PHASES OF CAD SYSTEM MORE CLOSELY SO THAT SIGNIFICANTLY ENHANCED ROUTING PERFORMANCE CAN BE EXPECTED. WE WILL EVALUATE OUR ALGORITHMS ON A NUMBER OF ARCHITECTURES INCLUDING A SMALL SCALE PARALLEL PROCESSOR DESIGNED AS A PERFORMANCE ACCELERATOR AND EDUCATIONAL TOOL FOR PC MACHINES.