This paper presents an efficient algorithm for multi-way balanced partitioning of VLSI circuits. The proposed algorithm is still based on the widely used net-cut model, but its novelty is the potential gain function into the net-cut cost function to relax the single-cell-move constraint (as commonly encountered in the Kernighan-Lin algorithm) for balanced partitioning. This feature permits to move a group of cells (referred to as a Multi-Cell-Move strategy) for partitioning a circuit, while reducing its sensitivity to size constraint. The new multi-way partitioning algorithm is fully analyzed; expressions for the potential gain function (with respect to the multi-move operation) and the cost (for the min-cut objective function) are presented. The time complexity of the proposed partitioning algorithm is O(P/spl times/k/sup 2/ log/sub 2/ (k)), where k is the number of blocks and P is the number of pins. Simulation results are presented and a remarkable improvement is achieved compared with existing algorithms, such as the k-Dual Part algorithm.

The Reconfigurable Array with Spanning Optical Buses (RASOB) has recently received a lot of attention from the research community. By taking advantage of the unique properties of optical transmission, the RASOB provides flexible reconfiguration and strong connectivities with low hardware and control complexities. In this paper, we use this architecture for the design of efficient sorting algorithms on the 1-D RASOB and the 2-D RASOB. Our parallel sorting algorithm on the 1-D RASOB, which sorts N data items using N processors in O(k) time where k is the size of the data items to be in bits, is based on a novel divide-and-conquer scheme. On the other hand, our parallel sorting algorithm on the 2-D RASOB is based on the sorting algorithm on the 1-D RASOB in conjunction with the well known Rotatesort algorithm. This algorithm sorts N data items on a 2-D RASOB of size N in O(k) time. These sorting algorithms outperform state-of-the-art sorting algorithms on reconfigurable arrays of processors with electronic buses.