Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
A Tight Layout of the Butterfly Network
| |
|
A Tight Layout of the Butterfly Network
A. Avior1, T. Calamoneri2, S. Even1, A. Litman1 and A. L. Rosenberg3
| (1) |
Computer Science Department, The Technion, Haifa 32000, Israel {aythan,even,litman}@cs.technion.ac.il , IL |
| (2) |
Computer Science Department, University of Rome ``La Sapienza,'' Via Salaria 113, 00198 Roma, Italy calamo@dsi.uniroma1.it
, IT |
| (3) |
Department of Computer Science, University of Massachusetts, Amherst, MA 01003, USA rsnbrg@cs.umass.edu, US |
Abstract. We establish upper and lower bounds on the layout area of the butterfly network (without wraparound), which differ only in
low-order terms. Specifically, the N -input, N -output butterfly network can be laid out in area (1 + o(1)) N
2
, while no layout of the network can have area smaller than (1 - o(1)) N
2
. These results improve both the known upper bound and the known lower bound on the area of butterfly network layouts.
Received October 1996, and in final form February 1997.
Fulltext Preview (Small, Large)
|
|
|
|
|
|