EXECUTION TIME – AREA TRADEOFF IN GAUSING RESIDUAL LOAD DECODER: INTEGRATED EXPLORATION OF CHAINING BASED SCHEDULE AND ALLOCATION IN HLS FOR HARDWARE ACCELERATORS

Anirban Sengupta, Reza Sedaghat, Vipul Kumar Mishra

DOI Number
-
First page
235
Last page
249

Abstract


Design space exploration is an indispensable segment of High Level Synthesis (HLS) design of hardware accelerators. This paper presents a novel technique for Area-Execution time tradeoff using residual load decoding heuristics in genetic algorithms (GA) for integrated design space exploration (DSE) of scheduling and allocation. This approach is also able to resolve issues encountered during DSE of data paths for hardware accelerators, such as accuracy of the solution found, as well as the total exploration time during the process. The integrated solution found by the proposed approach satisfies the user specified constraints of hardware area and total execution time (not just latency), while at the same time offers a twofold unified solution of chaining based schedule and allocation. The cost function proposed in the genetic algorithm approach takes into account the functional units, multiplexers and demultiplexers needed during implementation. The proposed exploration system (ExpSys) was tested on a large number of benchmarks drawn from the literature for assessment of its efficiency. Results indicate an average improvement in Quality of Results (QoR) greater than 26 % when compared to a recent well known GA based exploration method.

Full Text:

PDF

References


AnirbanSengupta, Reza Sedaghat, ZhipengZeng, “A High Level Synthesis design flow with a novel approach for Efficient Design Space Exploration in case of multi parametric optimization objective”, Microelectronics Reliability, Elsevier, Volume 50, Issue 3, March 2010, Pages 424-437.

C. Mandal, P. P. Chakrabarti, and S. Ghose, “GABIND: A GA approach to allocation and binding for the high-level synthesis of data paths,” IEEE Transaction on VLSI, vol. 8, no. 5, pp.747–750, Oct. 2000.

M. J. M. Heijlingers, L. J. M. Cluitmans, and J. A. G. Jess, “High-level synthesis scheduling and allocation using genetic algorithms,” in Proc. ASP-DAC., pp. 61–66, 1995.

M. K. Dhodhi, F. H. Hielscher, R. H. Storer, and J. Bhasker, “Datapath synthesis using a problem-space genetic algorithm,” in IEEE Trans.Comput.-Aided Des., vol. 14, pp. 934–944,1995.

I. Das. A preference ordering among various Pareto optimal alternatives. Structural and Multidisciplinary Optimization, 18(1):30–35, Aug. 1999.

Alessandro G. Di Nuovo, Maurizio Palesi, Davide Patti, Fuzzy Decision Making in Embedded System Design,” Proc. of 4th Intl Conference on Hardware/Software Codesign and System synthesis, pp: 223-228, October 2006.

J. C. Gallagher, S. Vigraham, and G. Kramer,“A family of compact genetic algorithms for intrinsic evolvable hardware,” IEEE Trans. Evolutionary Computation., vol. 8, no. 2 , pp. 1–126, Apr. 2004.

Vyas Krishnan and SrinivasKatkoori, “A Genetic Algorithm for the Design Space Exploration of DatapathsDuring High-Level Synthesis, IEEE Tran.on Evolutionary Computation, vol.10, no.3, 2006.

E. Torbey and J. Knight, “High-level synthesis of digital circuits using genetic algorithms,” in Proc. Int. Conf. Evol. Comput., pp.224–229, May 1998.

E. Torbey and J. Knight, “Performing scheduling and storage optimization simultaneously using genetic algorithms,” in Proc. IEEE Midwest Symp. Circuits Systems, pp. 284–287, 1998.

Giuseppe Ascia, Vincenzo Catania, Alessandro G. Di Nuovo, Maurizio Palesi, Davide Patti, “Efficient design space exploration for application specific systems-on-a-chip” Jrnl of Systems Architecture 53, pp:733–750, 2007.

A.C.Williams, A.D.Brown and M.Zwolinski,“Simultaneous optimisation of dynamic power, area and delay in behavioural synthesis”, IEE Proc.-Comput. Digit. Tech, Vol. 147, No. 6, pp: 383-390, 2000.

Christian Haubelt, Thomas Schlichter, Joachim Keinert, Mike Meredith, “SystemCoDesigner: automatic design space exploration and rapid prototyping from behavioral models”, Proceedings of the 45th annual ACM IEEE Design Automation Conference, Pages 580-585, 2008.

Xuejie Zhang and Kam W. Ng, “A review of high-level synthesis for dynamically reconfigurable FPGAs”, Microprocessors and Microsystems, Elsevier, Volume 24, Issue 4, Pages 199-211,1 2000.

N. Wehn et al., “A novel scheduling and allocation approach to datapath synthesis based on genetic paradigms,” in Proc. IFIPWorking Conf. Logic Architecture Synthesis, pp. 47–56, 1991.

R. M. San and J. P. Knoght, “Genetic algorithms for optimization of integrated circuit synthesis,” in Proc. 5th Int. Conf. Genetic Algorithms, San Mateo, CA, pp. 432–438, 1993.

R. J. Cloutier and D. E. Thomas, “The combination of scheduling, allocation and mapping in a single algorithm,” in Proc. 27th Design Automation Conf., pp. 71–76, Jun. 1990.

J. A. Nestor and G. Krishnamoorthy, “SALSA: A new approach to scheduling with timing constraints,” IEEE Trans. Comput.-Aided Des., vol. 12, pp. 1107–1122, 1993.

G. Krishnamoorthy and J. A. Nestor, “Data path allocation using extended binding model,” in Proc. 32nd ACM/IEEE Design Automation Conf., pp. 279–284, 1992.

S. Devadas and A. R. Newton, “Algorithms for hardware allocation in data path synthesis,” IEEE Trans. Comput.-Aided Des., vol. 8, pp.768–781, 1989.

T. A. Ly and J. T. Mowchenko, “Applying simulated evolution to high level synthesis,” IEEE Trans. Comput.-Aided Des., vol. 12, no. 2, pp.389–409, Feb. 1993.

C. H. Gebotys and M. I. Elmasry, “Global optimization approach for architectural synthesis,” IEEE Trans. Comput.-Aided Des., vol. 12, pp. 1266–1278, 1993.

C. T. Hwang, J. H. Lee, Y. C. Hsu, and Y. L. Lin, “A formal approach to the scheduling problem in high-level synthesis,” IEEE Trans. Comput.- Aided Des., vol. 10, no. 2, pp. 464–475, Feb. 1991.

G. De Micheli, Synthesis and Optimization of Digital Circuits. New York: McGraw-Hill, 1994.

R. Camposano, “Path-based scheduling for synthesis,” IEEE Trans.CAD., vol. 10, pp. 85–93, 1991.

P. G. Paulin and J. P. Knight, “Force-directed scheduling for the behavioral synthesis of ASICs,” IEEE Trans. Comput.-Aided Des., vol. 8, no.6, pp. 661–679, 1989.

A. C. Parker, J. T. Pizarro, and M. Mlinar, “Maha: A program for datapath synthesis,” in Proc. 23rd ACM/IEEE Design Automation Conf., 1986, pp. 461–466.

T. Blickle and L. Thiele, “A mathematical analysis of tournament selection,” in Proc. 6th Int. Conf. Genetic Algorithms, pp. 9–16, 1995.

http://www.cbl.ncsu.edu/benchmarks/.

Saraju P. Mohanty, NagarajanRanganathan, Elias Kougianos and PriyadarsanPatra, “Low-Power High-Level Synthesis for Nanoscale CMOS Circuits” Chapter- High-Level Synthesis Fundamentals, Springer US, 2008.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626