Abstract
We present a systolic array architecture to solve the problem of hypergraph partitioning. The architecture is based on a sophisticated search technique belonging to the class of genetic algorithms. A hypergraph is decomposed into a stream of fine grained, bit string data in which they are propagated into an array of locally connected processing elements. Although each processing element can handle only a few simple bit level Boolean operations, it is shown that the overall connected array forms a powerful hardware partitioning engine in which pipelining and parallelism are fully exploited. Three inner procedures in this GA based solution were parallelized, namely, the fitness evaluation, crossover and mutation operations. A time complexity analysis together with a brief logic block diagrams for the parallel architecture are presented. Simulated results indicated good speedup.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Yen Chuen Wei, Chung-Kuen Cheng, Ratio Cut Partitioning for Hierarchical Designs. IEEE Transactions on Computer-Aided Design Vol 10 No 7, July 1991.
Anthony Vannelli, and Scott W. Hadley and Brian L. Mark, An Efficient Eigenvector Approach for Finding Netlist Partitions. IEEE Transactions on CAD. Vol 11 No.7 July 1992.
J. H Holland, Adaptation in Natural and Artificial systems, Ann Arbor, The university of Michigan Press.
J. M. Speiser, H.J. Whitehouse, K. Bromley: Signal Processing Applications for Systolic Arrays. Naval Ocean System Center, San Diego, CA 92152, U.S.A.
E-G Talbi and P. Bessiere, A Parallel Genetic Algorithm for the Graph Partitioning Problem. International Conference on Supercomputing pp. 312–320, 1991.
T. N. Bui and B. R. Moon, A Fast and Stable Hybrid Genetic Algorithm for the Ratio-cut Partitioning Problem on Hypergraphs. 31st, IEEE Design Automation Conference, pp 664–668.
Hulin M, Circuit Partitioning With Genetic Algorithms Using a Coding Scheme to Preserve The Structure of A Circuit. Proceeding of the First Workshop on Parallel Problem Solving from Nature, pp 75–79.
K. Shahookar and P Mazumder, A Genetic Approach to Partitioning, private communication.
C.M. Fiduccia, and R.M. Matteyses, A Linear Time Heuristic for Improving Network Partitions, IEEE Design Automation Conference, pp 175–181, 1982.
L. Hagen and A. Kahng, New spectral Methods for Ratio Cut Partitioning and Clustering, IEEE Transactions on CAD 11 (9), Sept. 1992.
P. D. Hortensius, R. D. McLeod and H. C. Card, Parallel Random Number Generation for VLSI Systems Using Cellular Automata. IEEE Transactions on Computer, Vol 38, No 10 1989.
S. Wolfram, Statistical Mechanics of Cellular Automata. Rev, Modern Phys., vol 55 pp 601–644, 1983.
A. Bouloutas, P.M. Gopal, Some Graph Partitioning Problems and Algorithms Related to Routing in Large Computer Networks. 9th Int, Conf. on Distributed Computing Systems, pp 362–370, 1989.
L. Herault, J. J. Niez, How Neural Networks Can Solve Hard Graph Problems: A Performance Study on the Graph k-partitioning. Neuro-Nimes 89, Int. Workshop on Neural Network and Their Applications. Nimes, France, pp 237–255, Nov. 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chan, H., Mazumder, P. (1995). A systolic architecture for high speed hypergraph partitioning using a genetic algorithm. In: Yao, X. (eds) Progress in Evolutionary Computation. EvoWorkshops EvoWorkshops 1993 1994. Lecture Notes in Computer Science, vol 956. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60154-6_51
Download citation
DOI: https://doi.org/10.1007/3-540-60154-6_51
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60154-8
Online ISBN: 978-3-540-49528-4
eBook Packages: Springer Book Archive