Azadeh Davoodi
Abstract
This article proposes two very fast graph theoretic heuristics for the low power binding problem given fixed number of resources and multiple architectures for the resources. First, the generalized low power binding problem is formulated as an Integer Linear Programming (ILP) problem that happens to be an NP-complete task to solve. Then two polynomial-time heuristics are proposed that provide a speedup of up to 13.7 with an extremely low penalty for power when compared to the optimal ILP solution for our selected benchmarks.
- Boppana, R. and Halldórsson, M. M. 1990. Approximating maximum independent sets by excluding subgraphs. In Proceedings of the SWAT 90 2nd Scandinavian Workshop on Algorithm Theory 447, pp. 13--25.]] Google Scholar
- Bringmann, O. and Rosenstiel, W. 1997. Resource sharing in hierarchical synthesis. In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 318--325.]] Google Scholar
- Chandrakasan, A. P., Sheng, S., and Brodersen, R. W. 1992. Low power CMOS digital design. IEEE J. Solid State Circ. (Apr.) pp. 472--484.]]Google Scholar
- Chang, J.-M. and Pedram, M. 1995. Low power register allocation and binding. In Proceedings of the Design Automation Conference (June). pp. 29--35.]] Google Scholar
- Chang, J.-M. and Pedram, M. 1996. Module assignment for low-power. In Proceedings of the European Design Automation Conference (Sept.). pp. 376--381.]] Google Scholar
- Fang, Y. M. and Wong, D. F. 1994. Simultaneous functinal-unit binding and floorplanning. In Proceedings of the International Conference on Computer-Aided Design (Nov.). pp. 317--321.]] Google Scholar
- Hafer, L. and Parker, A. 1982. Automated synthesis of digital hardware. IEEE Trans. Comput., Feb.]]Google ScholarDigital Library
- Halldórsson, M. M. 1999. Approximations of weighted independent set and hereditary subset problems. In Proceedings of the 5th Annual International Conference on Computing and Combinatorics, Lecture Notes in Computer Science. Springer-Verlag, New York, pp. 261--270.]]Google Scholar
- Hashimoto, A. and Stevens, J. 1971. Wire routing by optimizaing channel assignment with large apertures. In Proceedings of the 8th Design Automation Workshop. pp. 155--169.]] Google Scholar
- Herrmann, D. and Ernstl, R. 1999. Improved interconnect sharing by identity operation insertion. In International Conference on Computer-Aided Design (Nov.). pp. 489--492.]] Google Scholar
- Kruse, L., Schmidt, E., Jochens, G., Stammermann, A., Schulz, A., Macii, E., and Nebel, W. 2001. Estimation of lower and upper bounds on the power consumption from scheduled data flow graphs. IEEE Trans. VLSI Syste. (Feb.). pp. 3--14.]] Google ScholarDigital Library
- Lee, C., Potkonjak, M., and Mangione-Smith, W. H. 1997. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the International Symposium on Microarchitecture.]] Google Scholar
- Niedermeier, R. and Rossmanith, P. 2000. On efficient fixed parameter algorithms for WEIGHTED VERTEX COVER. In Proceedings of the International Symposium on Algorithms and Computation, pp. 180--191.]] Google ScholarCross Ref
- Ogrenci-Memik, S., Bozorgzadeh, E., Kastner, R., and Sarrafzadeh, M. 2001. A super scheduler for embedded reconfigurable systems. In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 391--394.]] Google Scholar
- Raghunathan, A. and Jha, N. 1995. An ILP formulation for low power based on minimizing switched capacitance during datapath allocation. In Proceedings of the IEEE Symposium on Circuits and Systems.]]Google Scholar
- Raje, S. and Bergamaschi, R. A. 1977. Gerenralized resource sharing. In Proceedings of the International Conference on Computer Aided Design (Nov.). pp. 326--332.]] Google Scholar
- Srivastava, A. 2002. Predictability: Definition, analysis and optimization. In Proceedings of the International Conference on Computer Aided Design, Nov.]] Google Scholar
- Tseng, C. J. and Siewiorek, D. 1986. Automated synthesis of data paths in digital systems. IEEE Trans. Comput. Aid. Des. (July).]]Google Scholar
Index Terms
- Effective techniques for the generalized low-power binding problem
Recommendations
Effective graph theoretic techniques for the generalized low power binding problem
ISLPED '03: Proceedings of the 2003 international symposium on Low power electronics and designThis paper proposes two very fast graph theoretic heuristics for the low power binding problem given fixed number of resources and multiple architectures for the resources. First the generalized low power binding problem is formulated as an Integer ...
Scheduling and resource binding for low power
ISSS '95: Proceedings of the 8th international symposium on System synthesisAbstract: Decisions taken at the earliest steps of the design process may have a significant impact on the characteristics of the final implementation. This paper illustrates how power consumption issues can be tackled during the scheduling and resource-...
Comments