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 (US) |
|---|---|
| Pages (from-to) | 400-405 |
| Number of pages | 6 |
| Journal | IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers |
| State | Published - 1999 |
| Externally published | Yes |
| Event | Proceedings of the 1999 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-99) - San Jose, CA, USA Duration: Nov 7 1999 → Nov 11 1999 |
ASJC Scopus subject areas
- Software
- Computer Science Applications
- Computer Graphics and Computer-Aided Design