A Fast Algorithm for Finding Maximal Empty Rectangles for Dynamic FPGA Placement

	This Article
	PDF RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Manish Handa Articles by Ranga Vemuri

Design, Automation and Test in Europe Conference and Exhibition Volume I (DATE'04)

A Fast Algorithm for Finding Maximal Empty Rectangles for Dynamic FPGA Placement (PDF)

Paris, France

February 16-February 20

ISBN: 0-7695-2085-5

	ASCII Text	x
	Manish Handa, Ranga Vemuri, "A Fast Algorithm for Finding Maximal Empty Rectangles for Dynamic FPGA Placement," Design, Automation and Test in Europe Conference and Exhibition, vol. 1, pp. 10744, Design, Automation and Test in Europe Conference and Exhibition Volume I (DATE'04), 2004.

	BibTex	x
	@article{ 10.1109/DATE.2004.1268958, author = {Manish Handa and Ranga Vemuri}, title = {A Fast Algorithm for Finding Maximal Empty Rectangles for Dynamic FPGA Placement}, journal ={Design, Automation and Test in Europe Conference and Exhibition}, volume = {1}, year = {2004}, issn = {1530-1591}, pages = {10744}, doi = {http://doi.ieeecomputersociety.org/10.1109/DATE.2004.1268958}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Design, Automation and Test in Europe Conference and Exhibition TI - A Fast Algorithm for Finding Maximal Empty Rectangles for Dynamic FPGA Placement SN - 1530-1591 SP EP A1 - Manish Handa, A1 - Ranga Vemuri, PY - 2004 KW - null VL - 1 JA - Design, Automation and Test in Europe Conference and Exhibition ER -

Manish Handa, University of Cincinnati

Ranga Vemuri, University of Cincinnati

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DATE.2004.1268958

In this paper, we present a fast algorithm for finding empty area on the FPGA surface with some rectangular tasks placed on it. We use a staircase datastructure to report the empty area in the form of a list of maximal empty rectangles. We model the FPGA surface using an innovative encoding scheme that improves runtime and reduces memory requirement of our algorithm.Worst-case time complexity of our algorithm is O(xy) where x is number of columns, y is number of rows and x.y is the total number of cells on the FPGA.

Citation:

Manish Handa, Ranga Vemuri, "A Fast Algorithm for Finding Maximal Empty Rectangles for Dynamic FPGA Placement," date, vol. 1, pp.10744, Design, Automation and Test in Europe Conference and Exhibition Volume I (DATE'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.