Title :
On the complexity of optimal bused interconnections
Author :
Kulasinghe, Priyalal ; El-Amawy, Ahmed
Author_Institution :
Dept. of Electr. & Comput. Eng., Clarkson Univ., Potsdam, NY, USA
fDate :
10/1/1995 12:00:00 AM
Abstract :
This paper addresses the combinatorial problem of constructing a minimal cost, bused, interconnection among a set of modules (or processors). Although some work has been reported on bused interconnection between modules, the compuational complexity of the problem has not been previously addressed. We show that the optimization problem of finding a minimal cost interconnection among modules to realize a certain set of data transfers is NP-Hard
Keywords :
computational complexity; multiprocessor interconnection networks; NP-Hard; combinatorial problem; compuational complexity; data transfers; minimal cost interconnection; optimal bused interconnections complexity; optimization problem; Computational complexity; Cost function; Digital systems; Dynamic programming; Integrated circuit interconnections; Minimization; Multiprocessing systems; Pins; Polynomials; Upper bound;
Journal_Title :
Computers, IEEE Transactions on
