Deeper and Sparser Nets Are Optimal

Valeriu Beiu, Hanna E. Makaruk

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    The starting points of this paper are two size-optimal solutions: (1) one for implementing arbitrary Boolean functions (Home and Hush, 1994); and (2) another one for implementing certain sub-classes of Boolean functions (Red`kin, 1970). Because VLSI implementations do not cope well with highly interconnected nets--the area of a chip grows with the cube of the fan-in (Hammerstrom, 1988)--this paper will analyze the influence of limited fan-in on the size optimality for the two solutions mentioned. First, the authors will extend a result from Home and Hush (1994) valid for fan-in {Delta} = 2 to arbitrary fan-in. Second, they will prove that size-optimal solutions are obtained for small constant fan-in for both constructions, while relative minimum size solutions can be obtained for fan-ins strictly lower that linear. These results are in agreement with similar ones proving that for small constant fan-ins ({Delta} = 6...9) there exist VLSI-optimal (i.e., minimizing AT{sup 2}) solutions (Beiu, 1997a), while there are similar small constants relating to the capacity of processing information (Miller 1956).
    Original languageEnglish
    Title of host publicationInternational ICSC Symposium on Engineering of Intelligent Systems
    Publication statusPublished - Mar 1 1998
    EventEIS'98 - Tenerife, Canary Islands, Spain
    Duration: Feb 9 1998 → …


    Period2/9/98 → …


    Dive into the research topics of 'Deeper and Sparser Nets Are Optimal'. Together they form a unique fingerprint.

    Cite this