A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning

Huiqun Liu; D. F. Wong

doi:10.1109/ICCAD.1999.810683

A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning

Huiqun Liu, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

9 Citations (Scopus)

Abstract

This paper presents an optimal algorithm to solve the schedule compression problem, which is an open problem proposed by Trimberger for time-multiplexed FPGA partitioning. Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic. Schedule compression is an important step in partitioning for time-multiplexed FPGAs [1,4,9,10] and can greatly influence the quality of the partitioning solution. We exactly solve the schedule compression problem by converting it to a constrained min-max path problem. We further extend our algorithm to minimize the communication cost during schedule compression. Experiments show that our optimal algorithm outperforms the existing heuristics and runs very efficiently.

Original language	English
Title of host publication	1999 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers
Publisher	IEEE
Pages	400-405
Number of pages	6
ISBN (Print)	0780358325
DOIs	https://doi.org/10.1109/ICCAD.1999.810683
Publication status	Published - 7 Nov 1999
Event	1999 IEEE International Conference on Computer-Aided Design, ICCAD 1999 - San Jose, United States Duration: 7 Nov 1999 → 11 Nov 1999 https://ieeexplore.ieee.org/xpl/conhome/6570/proceeding (Conference proceedings) https://dl.acm.org/doi/proceedings/10.5555/339492

Publication series

Name	IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
ISSN (Print)	1092-3152
ISSN (Electronic)	1558-2434

Conference

Conference	1999 IEEE International Conference on Computer-Aided Design, ICCAD 1999
Country/Territory	United States
City	San Jose
Period	7/11/99 → 11/11/99
Internet address	https://ieeexplore.ieee.org/xpl/conhome/6570/proceeding (Conference proceedings) https://dl.acm.org/doi/proceedings/10.5555/339492

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1109/ICCAD.1999.810683

Cite this

Liu, H., & Wong, D. F. (1999). A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning. In 1999 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers (pp. 400-405). (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers). IEEE. https://doi.org/10.1109/ICCAD.1999.810683

@inproceedings{474e68420c114442a4084ee8857373b7,

title = "A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning",

abstract = "This paper presents an optimal algorithm to solve the schedule compression problem, which is an open problem proposed by Trimberger for time-multiplexed FPGA partitioning. Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic. Schedule compression is an important step in partitioning for time-multiplexed FPGAs [1,4,9,10] and can greatly influence the quality of the partitioning solution. We exactly solve the schedule compression problem by converting it to a constrained min-max path problem. We further extend our algorithm to minimize the communication cost during schedule compression. Experiments show that our optimal algorithm outperforms the existing heuristics and runs very efficiently.",

author = "Huiqun Liu and Wong, {D. F.}",

note = "This work was partially supported by the Texas Advanced Research Program under Grant No. 003658288. ; 1999 IEEE International Conference on Computer-Aided Design, ICCAD 1999 ; Conference date: 07-11-1999 Through 11-11-1999",

year = "1999",

month = nov,

day = "7",

doi = "10.1109/ICCAD.1999.810683",

language = "English",

isbn = "0780358325",

series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers",

publisher = "IEEE",

pages = "400--405",

booktitle = "1999 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/6570/proceeding, https://dl.acm.org/doi/proceedings/10.5555/339492",

}

Liu, H & Wong, DF 1999, A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning. in 1999 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers. IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, IEEE, pp. 400-405, 1999 IEEE International Conference on Computer-Aided Design, ICCAD 1999, San Jose, California, United States, 7/11/99. https://doi.org/10.1109/ICCAD.1999.810683

A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning. / Liu, Huiqun; Wong, D. F.
1999 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers. IEEE, 1999. p. 400-405 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning

AU - Liu, Huiqun

AU - Wong, D. F.

N1 - This work was partially supported by the Texas Advanced Research Program under Grant No. 003658288.

PY - 1999/11/7

Y1 - 1999/11/7

N2 - This paper presents an optimal algorithm to solve the schedule compression problem, which is an open problem proposed by Trimberger for time-multiplexed FPGA partitioning. Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic. Schedule compression is an important step in partitioning for time-multiplexed FPGAs [1,4,9,10] and can greatly influence the quality of the partitioning solution. We exactly solve the schedule compression problem by converting it to a constrained min-max path problem. We further extend our algorithm to minimize the communication cost during schedule compression. Experiments show that our optimal algorithm outperforms the existing heuristics and runs very efficiently.

AB - This paper presents an optimal algorithm to solve the schedule compression problem, which is an open problem proposed by Trimberger for time-multiplexed FPGA partitioning. Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic. Schedule compression is an important step in partitioning for time-multiplexed FPGAs [1,4,9,10] and can greatly influence the quality of the partitioning solution. We exactly solve the schedule compression problem by converting it to a constrained min-max path problem. We further extend our algorithm to minimize the communication cost during schedule compression. Experiments show that our optimal algorithm outperforms the existing heuristics and runs very efficiently.

UR - http://www.scopus.com/inward/record.url?scp=0033319376&partnerID=8YFLogxK

U2 - 10.1109/ICCAD.1999.810683

DO - 10.1109/ICCAD.1999.810683

M3 - Conference proceeding

AN - SCOPUS:0033319376

SN - 0780358325

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers

SP - 400

EP - 405

BT - 1999 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers

PB - IEEE

T2 - 1999 IEEE International Conference on Computer-Aided Design, ICCAD 1999

Y2 - 7 November 1999 through 11 November 1999

ER -

A graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this