Abstract
The channel-assignment problem is central to the integrated circuit fabrication process. Given a two-sided printed circuit board, we wish to maken pairs of components electrically equivalent. The connections are made using two vertical runs along with a horizontal one. Each horizontal run lies in a channel. The channel-assignment problem involves minimizing the total number of channels used.
Recent advances in VLSI have made it possible to build massively parallel machines. To overcome the inefficiency of long distance communications among processors, some parallel architectures have been augmented by bus systems. If such a bus system can be dynamically changed to suit communication needs among processors, it is referred to asreconfigurable. The reconfigurable mesh is one of the practical models featuring a reconfigurable bus system. In this paper, we propose a constant-time algorithm to solve the channel-assignment problem of sizen on a reconfigurable mesh of sizen×n.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
O. Berkman, D. Breslauer, Z. Galil, B. Schieber and U. Vishkin,Highly parallelizable problems, Proceedings of ST OC 1989, 770–785.
U. I. Gupta, D. T. Lee and J. Y. T. Leung,An optimal solution for the channel assignment problem, IEEE Trans. Comput. 28 (1979) 807–810.
J.-W. Jang and V. K. Prasanna,An optimal sorting algorithm on reconfigurable meshes, USC Tech. Report IRIS #277, August, 1991.
S. K. Kim,Optimal parallel algorithms on sorted intervals, Proceeding of the 27th Annual Allerton Conference on Communications, Control and Computing '89, 766–775.
H. Li and M. Maresca,Polymorphic-torus network, IEEE Transactions on Computers, Vol. C-38, no. 9, (1989) 1345–1351.
R. Lin, S. Olariu, J. L. Schwing and J. Zhang,Sorting in O(1)time on an n × n reconfigurable mesh. Proceedings of the Ninth European Workshop on Parallel Computing, Barcelona, Spain, March, 1992, to appear.
M. Maresca and H. Li,Connection autonomy and SIMD computers: a V LSI implementation. Journal of Parallel and Distributed Computing, 8 (1989) 302–320.
R. Miller, V. P. Kumar, D. Reisis and Q. F. Stout,Meshes with reconfigurable buses, Proceedings of the fifth MIT Conference on Advanced Research in VLSI, (1988) 163–178.
R. Miller, V. P. Kumar, D. Reisis and Q. F. Stout,Data movement operations and applications on reconfigurable VLSI arrays, Proceedings of the International Conference on Parallel Processing, 1, (1988) 205–208.
K. Nakato, T. Msuzawa and N. Tokura,A fast sorting algorithm on a reconfigurable array, The Institute of Electronics, Information and Communication Engineers, Japan, COMP 90-69, December 1990.
S. Olariu, J. L. Schwing and J. Zhang,Fundamental algorithms on reconfigurable meshes, Proc. 29th Annual Allerton Conference on Communications, Control, and Computing, 1991, 811–820.
S. Olariu, J. L. Schwing and J. Zhang,Fast computer vision algorihms for reconfigurable meshes, Proc. International Parallel Processing Symposium, Beverly Hills, March 1992, to appear.
S. Olariu, J. L. Schwing and J. Zhang,Time-optimal storing and applications on n × n enhanced meshes, Proceedings of the IEEE International Conference on Computer Systems and Software Engineering, The Hague, The Netherlands, May 1992, to appear.
B. T. Preas and M. J. Lorenzetti,Physical Design Automation of VLSI Systems, Benjamin/Cummings, Menlo Park, California, 1988.
Z. Syed, A. El Gamal and M. A. Breuer,On routing for custom integrated cricuits, Proc. 19th Design Automation Conference, 1982, 887–893.
S. Tsukiyama, E. S. Kuh and I. Shirakawa,An algorithm for single-row routing with prescribed street congestions, IEEE Trans. on Circuits and Systems, CAS-27, (1980) 765–771.
B. F. Wang and G. H. Chen,Constant time algorithms for sorting and computing convex hulls, Proc. Internat. Comp. Symp., Taiwan, 1990, 607–612.
Author information
Authors and Affiliations
Additional information
This work was supported by NASA under grant NCC1-99.
Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.
Rights and permissions
About this article
Cite this article
Olariu, S., Schwing, J.L. & Zhang, J. A constant-time channel-assignment algorithm on reconfigurable meshes. BIT 32, 586–597 (1992). https://doi.org/10.1007/BF01994843
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01994843