On the construction of universal series-parallel functions for logic module design

F. Y. Young, Martin D F Wong

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

Abstract

The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique, it is desirable to design FPGA logic modules based on Boolean functions which can be represented by a tree of gates (i.e. series-parallel or SP functions). In [5], the authors studied this issue and demonstrated the advantages of designing logic modules as universal SP functions, i.e. SP functions which can implement all SP functions with a certain number of inputs. However, the universal SP functions presented in [5] were designed manually and an automatic generation of universal SP functions was left as an open problem. In this paper, we present an algorithm to generate, for each n>0, a universal SP function for implementing all n-input SP functions. We also present an efficient Boolean matching algorithm for matching functions to the universal SP functions that we constructed. As it is important to have alternative universal SP functions from which logic-module designers can choose a design taking other criteria (e.g. area, delay, or power) into consideration, we developed an algorithm to generate alternative universal SP functions. In particular, we have found all universal SP functions for n-input SP functions, when n≤6.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Conference on Computer Design
Subtitle of host publicationVLSI in Computers and Processors
Editors Anon
PublisherIEEE
Pages482-488
Number of pages7
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 International Conference on Computer Design - Austin, TX, USA
Duration: Oct 12 1997Oct 15 1997

Other

OtherProceedings of the 1997 International Conference on Computer Design
CityAustin, TX, USA
Period10/12/9710/15/97

Fingerprint

Boolean functions
Trees (mathematics)
Field programmable gate arrays (FPGA)

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Young, F. Y., & Wong, M. D. F. (1997). On the construction of universal series-parallel functions for logic module design. In Anon (Ed.), Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors (pp. 482-488). IEEE.

On the construction of universal series-parallel functions for logic module design. / Young, F. Y.; Wong, Martin D F.

Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors. ed. / Anon. IEEE, 1997. p. 482-488.

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

Young, FY & Wong, MDF 1997, On the construction of universal series-parallel functions for logic module design. in Anon (ed.), Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors. IEEE, pp. 482-488, Proceedings of the 1997 International Conference on Computer Design, Austin, TX, USA, 10/12/97.
Young FY, Wong MDF. On the construction of universal series-parallel functions for logic module design. In Anon, editor, Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors. IEEE. 1997. p. 482-488
Young, F. Y. ; Wong, Martin D F. / On the construction of universal series-parallel functions for logic module design. Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors. editor / Anon. IEEE, 1997. pp. 482-488
@inproceedings{5bdb8e8d42bd45dbb8b4d486b6ef002c,
title = "On the construction of universal series-parallel functions for logic module design",
abstract = "The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique, it is desirable to design FPGA logic modules based on Boolean functions which can be represented by a tree of gates (i.e. series-parallel or SP functions). In [5], the authors studied this issue and demonstrated the advantages of designing logic modules as universal SP functions, i.e. SP functions which can implement all SP functions with a certain number of inputs. However, the universal SP functions presented in [5] were designed manually and an automatic generation of universal SP functions was left as an open problem. In this paper, we present an algorithm to generate, for each n>0, a universal SP function for implementing all n-input SP functions. We also present an efficient Boolean matching algorithm for matching functions to the universal SP functions that we constructed. As it is important to have alternative universal SP functions from which logic-module designers can choose a design taking other criteria (e.g. area, delay, or power) into consideration, we developed an algorithm to generate alternative universal SP functions. In particular, we have found all universal SP functions for n-input SP functions, when n≤6.",
author = "Young, {F. Y.} and Wong, {Martin D F}",
year = "1997",
language = "English (US)",
pages = "482--488",
editor = "Anon",
booktitle = "Proceedings - IEEE International Conference on Computer Design",
publisher = "IEEE",

}

TY - GEN

T1 - On the construction of universal series-parallel functions for logic module design

AU - Young, F. Y.

AU - Wong, Martin D F

PY - 1997

Y1 - 1997

N2 - The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique, it is desirable to design FPGA logic modules based on Boolean functions which can be represented by a tree of gates (i.e. series-parallel or SP functions). In [5], the authors studied this issue and demonstrated the advantages of designing logic modules as universal SP functions, i.e. SP functions which can implement all SP functions with a certain number of inputs. However, the universal SP functions presented in [5] were designed manually and an automatic generation of universal SP functions was left as an open problem. In this paper, we present an algorithm to generate, for each n>0, a universal SP function for implementing all n-input SP functions. We also present an efficient Boolean matching algorithm for matching functions to the universal SP functions that we constructed. As it is important to have alternative universal SP functions from which logic-module designers can choose a design taking other criteria (e.g. area, delay, or power) into consideration, we developed an algorithm to generate alternative universal SP functions. In particular, we have found all universal SP functions for n-input SP functions, when n≤6.

AB - The structural tree-based mapping algorithm is an efficient and popular technique for technology mapping. In order to make good use of this mapping technique, it is desirable to design FPGA logic modules based on Boolean functions which can be represented by a tree of gates (i.e. series-parallel or SP functions). In [5], the authors studied this issue and demonstrated the advantages of designing logic modules as universal SP functions, i.e. SP functions which can implement all SP functions with a certain number of inputs. However, the universal SP functions presented in [5] were designed manually and an automatic generation of universal SP functions was left as an open problem. In this paper, we present an algorithm to generate, for each n>0, a universal SP function for implementing all n-input SP functions. We also present an efficient Boolean matching algorithm for matching functions to the universal SP functions that we constructed. As it is important to have alternative universal SP functions from which logic-module designers can choose a design taking other criteria (e.g. area, delay, or power) into consideration, we developed an algorithm to generate alternative universal SP functions. In particular, we have found all universal SP functions for n-input SP functions, when n≤6.

UR - http://www.scopus.com/inward/record.url?scp=0031357426&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031357426&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0031357426

SP - 482

EP - 488

BT - Proceedings - IEEE International Conference on Computer Design

A2 - Anon, null

PB - IEEE

ER -