MAHA: A Program for Datapath Synthesis

TLDR

MAHA implements an algorithm for register‑level synthesis of datapaths from data‑flow specifications. The algorithm assigns critical‑path nodes linearly, then schedules nodes with the least freedom first, optimizing either cost under a time constraint or speed under a cost constraint. The implementation, written in Franz LISP, runs in minutes on a VAX 11/780 for practical‑size problems and is illustrated with literature examples.

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.