Uma proposta de implementação do algoritmo de Lee no multiprocessador Multiplus

Abstract

This paper discusses some issues concerning the implementation of Lee's routing algorithm on MULTIPLUS, a multiprocessor under development at NCE/UFRJ. MULTIPLUS supports up to 2048 processing nodes which can be organized into 32 clusters consisting of up to 8 processing nodes. The overall global memory address space is 32 Gbytes, which is physically distributed into modules of up to 32 Mbytes that are local to the processing nodes. The proposed implementation takes advantage of the memory hierarchy and partition within MULTIPLUS architecture to efficiently exploit the intrinsic parallelism of the expansion and reset phases of the algorithm. In addition, the proposed implementation is also able to perform in parallel the routing of nets constrained to non-overlapping layout areas.