Article

Free access

MAHA: a program for datapath synthesis

Authors:

Alice C. Parker,

Jorge T. Pizarro,

Mitch MlinarAuthors Info & Claims

DAC '86: Proceedings of the 23rd ACM/IEEE Design Automation Conference

Pages 461 - 466

Published: 02 July 1986 Publication History

PDF eReader

Abstract

MAHA is a program which implements an algorithm for register level synthesis of data paths from a data flow specification. The algorithm is based on a linear hardware assignment to critical path nodes, followed by a cost-based assignment using the concept of the freedom of a node to be scheduled. Functions with the least scheduling freedom are scheduled first. The program either minimizes cost, subject to a time constraint, or maximizes speed subject to a cost constraint. The implementation of this algorithm is presented using examples from the literature.

MAHA is written in Franz LISP, and executes within minutes for problems of practical size on a VAX 11/780.

References

[1]

Girczyc, E. F. and Knight, J. P. An ADA to Standard Cell Hardware Compiler Based on Graph Grammers and Scheduling. Proceedings of the ICCD '84, IEEE Computer Society, October, 1984.

Google Scholar

[2]

Granacki, J., Knapp, D., and Parker, A. The ADAM Advanced Design Automation System: Overview, Planner and Natural Language Interface. Proceedings of the 22nd Design Automation Conference, ACM-IEEE, June, }L985.

Digital Library

Google Scholar

[3]

Hitchcock, C.Y. Automated Synthesis of Data Paths. Master Th., Carnegie-Mellon University,1983.

Google Scholar

[4]

Knapp, D. and Parker, A. A Data Structure for VLSI Synthesis and Verification. Digital Integrated Systems Center, Dept. of EE-Systems, University of Southern California, October, 1983.

Google Scholar

[5]

Kurdahi, F. and Parker, A. Area Estimation of VLSI Integrated Circuits. CRI-85-05, EE-Systems Dept. USC, 1985.

Google Scholar

[6]

McFarland, M.C. Allocating Registers, Processors and Connections. Internal Carnegie-Mellon University Report.

Google Scholar

[7]

Nagle, A., Cloutier, R., and Parker, A. mSynthesis of Hardware for the Control of Digital Systems'. IEEE Transactions on Computer-Aided Design CAD-l, 4 (l~S2), ~01-212.

Digital Library

Google Scholar

[8]

Park, N. and Parker, A. Synthesis of Optimal Clocking Sehemes. Proeeedings of the 22nd Design Automation Conference, ACM IEEE, June, 1985.

Digital Library

Google Scholar

[9]

Park, N. and Parker, A. Synthesis of Optimal Pipeline Clocking Schemes. DISC/85-1, Dept. of EE-System,~, University of Southern California, January, 1985.

Google Scholar

[10]

RCA. Integrated Computer Aided Design and Design Automation System. Second edition, RCA, Advan,zed Technology Labs., Moorestown,N.J., 1985. 3-MicrorL Standard Cell Library.

Google Scholar

Cited By

View all

Gu ZWan WXie JWu C(2021)Dependency Graph-based High-level Synthesis for Maximum Instruction ParallelismACM Transactions on Reconfigurable Technology and Systems10.1145/346887514:4(1-15)Online publication date: 13-Sep-2021
https://dl.acm.org/doi/10.1145/3468875
Dai SLiu GZhang ZAnderson JBazargan K(2018)A Scalable Approach to Exact Resource-Constrained Scheduling Based on a Joint SDC and SAT FormulationProceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3174243.3174268(137-146)Online publication date: 15-Feb-2018
https://dl.acm.org/doi/10.1145/3174243.3174268
Kritikakou ACatthoor FKelefouras VGoutis C(2013)A systematic approach to classify design-time global scheduling techniquesACM Computing Surveys10.1145/2431211.243121345:2(1-30)Online publication date: 12-Mar-2013
https://dl.acm.org/doi/10.1145/2431211.2431213
Show More Cited By

Index Terms

MAHA: a program for datapath synthesis
1. Applied computing
  1. Physical sciences and engineering
    1. Engineering
2. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
      1. Datapath optimization

Recommendations

Due date assignments and scheduling a single machine with a general earliness/tardiness cost function

We study three different due date assignment problems in scheduling a single machine which differ from each other based upon the objective function and due date assignment method being used. Two different objective functions are considered. The first is ...
Single machine batch scheduling problem with fuzzy batch size

In a batch scheduling problem, jobs are grouped (group is called batch) and scheduled in batches, and a setup time is incurred when starting a new batch. Processing times are assumed to be identical for all jobs. Setup times are assumed to be identical ...
A study of storage assignment problem for an order picking line in a pick-and-pass warehousing system

Order picking is one of the most crucial factors for efficient warehouse management. Most of previous research in order picking in a warehouse considered only the picker-to-part or part-to-picker system; however, the pick-and-pass system plays an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '86: Proceedings of the 23rd ACM/IEEE Design Automation Conference

July 1986

835 pages

ISBN:0818607025

Chairman:
Don Thomas
IBM, Thomas J. Watson Research Center, Yorktown Heights, NY

Publisher

IEEE Press

Publication History

Published: 02 July 1986

Check for updates

Qualifiers

Article

Acceptance Rates

DAC '86 Paper Acceptance Rate 124 of 300 submissions, 41%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
383
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gu ZWan WXie JWu C(2021)Dependency Graph-based High-level Synthesis for Maximum Instruction ParallelismACM Transactions on Reconfigurable Technology and Systems10.1145/346887514:4(1-15)Online publication date: 13-Sep-2021
https://dl.acm.org/doi/10.1145/3468875
Dai SLiu GZhang ZAnderson JBazargan K(2018)A Scalable Approach to Exact Resource-Constrained Scheduling Based on a Joint SDC and SAT FormulationProceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3174243.3174268(137-146)Online publication date: 15-Feb-2018
https://dl.acm.org/doi/10.1145/3174243.3174268
Kritikakou ACatthoor FKelefouras VGoutis C(2013)A systematic approach to classify design-time global scheduling techniquesACM Computing Surveys10.1145/2431211.243121345:2(1-30)Online publication date: 12-Mar-2013
https://dl.acm.org/doi/10.1145/2431211.2431213
Karfa CMandal CSarkar D(2012)Formal verification of code motion techniques using data-flow-driven equivalence checkingACM Transactions on Design Automation of Electronic Systems10.1145/2209291.220930317:3(1-37)Online publication date: 5-Jul-2012
https://dl.acm.org/doi/10.1145/2209291.2209303
Beidas RMong WZhu J(2011)Register pressure aware scheduling for high level synthesisProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950911(461-466)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950911
Cong JZhang ZSentovich E(2006)An efficient and versatile scheduling algorithm based on SDC formulationProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147025(433-438)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1147025
Cordone RFerrandi FSantambrogio MPalermo GSciuto DHirose F(2006)Using speculative computation and parallelizing techniques to improve scheduling of control based designsProceedings of the 2006 Asia and South Pacific Design Automation Conference10.1145/1118299.1118502(898-904)Online publication date: 24-Jan-2006
https://dl.acm.org/doi/10.1145/1118299.1118502
Srivastava AMemik SChoi BSarrafzadeh M(2003)Achieving Design Closure Through Delay Relaxation ParameterProceedings of the 2003 IEEE/ACM international conference on Computer-aided design10.5555/996070.1009868Online publication date: 9-Nov-2003
https://dl.acm.org/doi/10.5555/996070.1009868
Kuchcinski KWolinski C(2003)Global approach to assignment and scheduling of complex behaviors based on HCDG and constraint programmingJournal of Systems Architecture: the EUROMICRO Journal10.1016/S1383-7621(03)00075-449:12-15(489-503)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1016/S1383-7621%2803%2900075-4
Cabodi GLazarescu MLavagno LNocco SPasserone CQuer SAboulhamid ENakamura Y(2002)A symbolic approach for the combined solution of scheduling and allocationProceedings of the 15th international symposium on System Synthesis10.1145/581199.581252(237-242)Online publication date: 2-Oct-2002
https://dl.acm.org/doi/10.1145/581199.581252
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Due date assignments and scheduling a single machine with a general earliness/tardiness cost function

Single machine batch scheduling problem with fuzzy batch size

A study of storage assignment problem for an order picking line in a pick-and-pass warehousing system