Majority operation has been paid attention as a basic element of beyond-Moore devices on which logic functions are constructed from Majority elements and inverters. Several optimization methods are developed to reduce the number of elements on Majority-Inverter Graphs (MIGs) but more area and power reduction are required. The paper proposes a new exact synthesis method for MIG based on a new topological constraint using node levels. Possible graph structures are clustered by the levels of input nodes, and all possible structures can be enumerated efficiently in the exact synthesis compared with previous methods. Experimental results show that our method decreases the runtime up to 25.33% compared with the fence-based method, and up to 6.95% with the partial-DAG-based method. Furthermore, our implementation can achieve better performance in size optimization for benchmark suites.
Xianliang GE
Waseda University
Shinji KIMURA
Waseda University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Xianliang GE, Shinji KIMURA, "Theory and Application of Topology-Based Exact Synthesis for Majority-Inverter Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 9, pp. 1241-1250, September 2023, doi: 10.1587/transfun.2022EAP1103.
Abstract: Majority operation has been paid attention as a basic element of beyond-Moore devices on which logic functions are constructed from Majority elements and inverters. Several optimization methods are developed to reduce the number of elements on Majority-Inverter Graphs (MIGs) but more area and power reduction are required. The paper proposes a new exact synthesis method for MIG based on a new topological constraint using node levels. Possible graph structures are clustered by the levels of input nodes, and all possible structures can be enumerated efficiently in the exact synthesis compared with previous methods. Experimental results show that our method decreases the runtime up to 25.33% compared with the fence-based method, and up to 6.95% with the partial-DAG-based method. Furthermore, our implementation can achieve better performance in size optimization for benchmark suites.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022EAP1103/_p
Copy
@ARTICLE{e106-a_9_1241,
author={Xianliang GE, Shinji KIMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Theory and Application of Topology-Based Exact Synthesis for Majority-Inverter Graphs},
year={2023},
volume={E106-A},
number={9},
pages={1241-1250},
abstract={Majority operation has been paid attention as a basic element of beyond-Moore devices on which logic functions are constructed from Majority elements and inverters. Several optimization methods are developed to reduce the number of elements on Majority-Inverter Graphs (MIGs) but more area and power reduction are required. The paper proposes a new exact synthesis method for MIG based on a new topological constraint using node levels. Possible graph structures are clustered by the levels of input nodes, and all possible structures can be enumerated efficiently in the exact synthesis compared with previous methods. Experimental results show that our method decreases the runtime up to 25.33% compared with the fence-based method, and up to 6.95% with the partial-DAG-based method. Furthermore, our implementation can achieve better performance in size optimization for benchmark suites.},
keywords={},
doi={10.1587/transfun.2022EAP1103},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Theory and Application of Topology-Based Exact Synthesis for Majority-Inverter Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1241
EP - 1250
AU - Xianliang GE
AU - Shinji KIMURA
PY - 2023
DO - 10.1587/transfun.2022EAP1103
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2023
AB - Majority operation has been paid attention as a basic element of beyond-Moore devices on which logic functions are constructed from Majority elements and inverters. Several optimization methods are developed to reduce the number of elements on Majority-Inverter Graphs (MIGs) but more area and power reduction are required. The paper proposes a new exact synthesis method for MIG based on a new topological constraint using node levels. Possible graph structures are clustered by the levels of input nodes, and all possible structures can be enumerated efficiently in the exact synthesis compared with previous methods. Experimental results show that our method decreases the runtime up to 25.33% compared with the fence-based method, and up to 6.95% with the partial-DAG-based method. Furthermore, our implementation can achieve better performance in size optimization for benchmark suites.
ER -