Cid C. de Souza
Guido Araujo
Abstract
In this paper, we investigate the data path merging problem (DPM) in reconfigurable systems. DPM is modeled as a graph optimization problem and is shown to be NP-hard. An Integer Programming (IP) formulation of the problem is presented and some valid inequalities for the convex hull of integer solutions are introduced. These inequalities form the basis of a branch-and-cut algorithm that we implemented. This algorithm was used to compute lower bounds for a set of DPM instances, allowing us to assess the performance of two heuristics proposed earlier in the literature for the problem. Moreover, the branch-and-cut algorithm also was proved to be a valuable tool to solve small-sized DPM instances to optimality.
- Battiti, R. and Protasi, M. 2001. Reactive local search for the maximum clique problem. Algorithmica 29, 4 (April), 610--637. C++ code available at http://rtm.science.unitn.it/intertools/clique/.Google Scholar
Digital Library
- Bondalapati, K. and Prasanna, V. 2002. Reconfigurable computing systems. Proceedings of the IEEE 90, 7 (July), 1201--1217.Google ScholarCross Ref
- Brisk, P., Kaplan, A., and Sarrafzadeh, M. 2004. Area-efficient instruction set synthesis for reconfigurable system-on-chip designs. In Proceedings of the Design Automation Conference (DAC). 395--400. Google ScholarDigital Library
- Callahan, T., Hauser, J., and Wawrzynek, J. 2000. The Garp architecture and C compiler. IEEE Computer 33, 4 (April), 62--69. Google ScholarDigital Library
- Compton, K. and Hauck, S. 2002. Reconfigurable computing: A survey of systems and software. ACM Computing Surveys 34, 2 (June), 171--210. Google ScholarDigital Library
- DeHon, A. and Wawrzynek, J. 1999. Reconfigurable computing: What, why, and implications for design automation. In Proceedings of the Design Automation Conference (DAC). 610--615. Google ScholarDigital Library
- Garey, M. and Johnson, D. S. 1979. Computers and Intractability---A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA. Google ScholarDigital Library
- Geurts, W., Catthoor, F., Vernalde, S., and De Man, H. 1997. Accelerator Data-path Synthesis for High-Throughput Signal Processing Applications. Kluwer Academic Publishers. Boston, MA. Google ScholarDigital Library
- Grötschel, M., Lovász, L., and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169--197.Google ScholarCross Ref
- Huang, Z. and Malik, S. 2001. Managing dynamic reconfiguration overhead in systems-on-a-chip design using reconfigurable data paths and optimized interconnection networks. In Proceedings of the Design, Automation, and Test in Europe Conference (DATE). 735--740. Google ScholarDigital Library
- Lee, C., Potkonjak, M., and Mangione-Smith, W. 1997. Mediabench: a tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the 30th Annual International Symposium on Microarchitecture (Micro '97). IEEE, Research Triangle Park, NC. 330--337. Benchmarks available at http://cares.icsl.ucla.edu/MediaBench/. Google ScholarDigital Library
- Mathur, A. and Saluja, S. 2001. Improved merging of data path operators using information content and required precision analysis. In Proceedings of the Design Automation Conference (DAC). 462--467. Google ScholarDigital Library
- Moreano, N., Araujo, G., Huang, Z., and Malik, S. 2002. Datapath merging and interconnection sharing for reconfigurable architectures. In Proceedings of the 15th International Symposium on System Synthesis. 38--43. Google ScholarDigital Library
- Moreano, N., Araujo, G., and de Souza, C. C. 2003. CDFG merging for reconfigurable architectures. Tech. Rep. IC-03-18, Institute of Computing, University of Campinas SP, Brazil.Google Scholar
- Nemhauser, G. L. and Wolsey, L. 1988. Integer and Combinatorial Optimization. Wiley, New York. Google ScholarDigital Library
- Papadimitriou, C. H. and Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity. Mineola, NY: Dover Publications. Google ScholarDigital Library
- Schaumont, P., Verbauwhede, I., Keutzer, K., and Sarrafzadeh, M. 2001. A quick safari through the reconfiguration jungle. In Proceedings of the Design Automation Conference (DAC). 172--177. Google ScholarDigital Library
- Schmit, H. et al. 2002. PipeRench: A virtualized programmable data path in 0.18 micron technology. In Proceedings of the IEEE Custom Integrated Circuits Conference (CICC). 63--66.Google Scholar
- Shirazi, N., Luk, W., and Cheung, P. 1998. Automating production of run-time reconfigurable designs. In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM). 147--156. Google ScholarDigital Library
- Singh, H., Lee, M., Lu, G., Kurdahi, F., Bagherzadeh, N., and Filho, E. 2000. MorphoSys: An integrated reconfigurable system for data-parallel and computation-intensive applications. IEEE Transactions on Computers 49, 5 (May), 465--481. Google ScholarDigital Library
- Werf, A. et al. 1992. Area optimization of multi-functional processing units. In Proceedings of the 1992 International Conference on Computer-Aided Design (ICCAD). 292--299. Google ScholarDigital Library
- Wolf, W. 2001. Computers as Components---Principles of Embedded Computing System Design. Morgan Kaufmann, San Mateo, CA. Google ScholarDigital Library
Index Terms
- The datapath merging problem in reconfigurable systems: Complexity, dual bounds and heuristic evaluation
Recommendations
A tabu search algorithm for the quadratic assignment problem
Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). ...
Branch-and-bound algorithm for the maximum triangle packing problem
We introduce a new branch-and-bound algorithm for the maximum triangle packing problem.The branch-and-bound algorithm uses a lower bound based on neighborhood degree.We present a novel upper bound based on a surrogate relaxation of the related ILP.Our ...
The Multidimensional Knapsack Problem: Structure and Algorithms
We study the multidimensional knapsack problem, present some theoretical and empirical results about its structure, and evaluate different integer linear programming (ILP)-based, metaheuristic, and collaborative approaches for it. We start by ...
Comments