Article by Timothy J. Callahan, Philip Chong, André DeHon, and John Wawrzynek, published in Proceedings of the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays (FPGA '98, February 22-24, 1998), 10 pages.
Abstract:
By tailoring a compiler tree-parsing tool for datapath module mapping, we produce good quality results for datapath synthesis in very fast run time. Rather than flattening the design to gates, we preserve the datapath structure; this allows exploitation of specialized datapath features in FPGAs, retains regularity, and also results in a smaller problem size. To further achieve high mapping speed, we formulate the problem as tree covering and solve it efficiently with a linear-time dynamic programming algorithm. In a novel extension to the tree-covering algorithm, we perform module placement simultaneously with the mapping, still in linear time. Integrating placement has the potential to increase the quality of the result since we can optimize total delay including routing delays.To our knowledge this is the first effort to leverage a grammar-based tree covering tool for datapath module mapping. Further, it is the first work to integrate simultaneous placement with module mapping in a way that preserves linear time complexity.
Gama.pdf [111 kB].
Gama.zip [70 kB].
Gama.ps.gz [70 kB].
Gama.ps.Z [108 kB].
Gama.ps [341 kB].
Errata for version published at FPGA'98:
More recent (2002):