A PARALLEL SIMULATED ANNEALING-BASED CHANNEL ROUTER

作     者：R. MALL SRILATA RAMAN L.M. PATNAIK 

作者机构：Motorola India Electronics Ltd The Presidency #1 St. Marks Road Bangalore 560 001 India Dept. of Electrical and Computer Engineering and Coordinated Science Laboratory University of Illinois at Urbana-Champaign IL 61801 USA Microprocessor Applications Laboratory Indian Institute of Science Bangalore 560 012 India 

出 版 物：《International Journal of High Speed Computing》 

年 卷 期：1994年第6卷第1期

页      面：101-114页

主　　题：Parallel algorithms channel routers hypercube architecture simulated annealing algorithm 

摘      要：The routing problem of VLSI layout design is very compute intensive. Consequently, the routing task often turns out to be a bottleneck in the layout design of large circuits. Parallel processing of the routing problem holds promise for mitigating this situation. In this context, we present a parallel channel routing algorithm that is targetted to run on loosely coupled computers like hypercubes. The proposed parallel algorithm employs the simulated annealing technique for obtaining near- optimum solutions. Initially, the number of tracks in the channel is made equal to the number of nets, and partitions of the channel are appropriately assigned to the nodes of the hypercube. Each node carries out concurrent perturbations to obtain new channel states that satisfy the constraints for a given net list. The algorithm minimizes the number of tracks iteratively by using the simulated annealing technique. For efficient execution, we attempt to reduce the communication overheads by restricting the broadcast updates to cases of interprocessor net transfers only. Performance evaluation studies of the algorithm show promising results.