The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article présente un algorithme heuristique appelé CLASSIC pour la minimisation de la largeur de la mémoire de contrôle dans les processeurs microprogrammés ou de la largeur de la mémoire d'instruction des processeurs VLIW (Very Long Instruction Word) spécifiques à une application. CLASSIC aboutit à des solutions presque optimales avec la complexité temporelle de O(n2), où n désigne le nombre de microopérations. Dans cet article, nous proposons également ce que l'on appelle relations d'incomplétude qui sont exploités pour la minimisation de la largeur de la mémoire de contrôle. Des expériences utilisant divers exemples ont montré que CLASSIC atteint toujours des largeurs de microprogramme plus petites par rapport aux techniques antérieures basées sur la classe de compatibilité maximale ou sur l'ensemble ET/OU minimal. Les résultats montrent que CLASSIC peut réduire la largeur de la mémoire de contrôle de 34.2 % en moyenne par rapport à un algorithme de classe de compatibilité heuristique.
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.
Copier
Young-doo CHOI, In-Cheol PARK, Chong-Min KYUNG, "CLASSIC: An O(n2)-Heuristic Algorithm for Microcode Bit Optimization Based on Incompleteness Relations" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 5, pp. 901-908, May 2000, doi: .
Abstract: This paper presents a heuristic algorithm called CLASSIC for the minimization of the control memory width in microprogrammed processors or the instruction memory width of application-specific VLIW (Very Long Instruction Word) processors. CLASSIC results in nearly optimal solutions with the time complexity of O(n2), where n denotes the number of microoperations. In this paper, we also propose the so-called incompleteness relations which are exploited for the minimization of the control memory width. Experiments using various examples have shown that CLASSIC always achieves smaller microprogram widths compared to the earlier techniques based on the maximal compatibility class or the minimal AND/OR set. The results show that CLASSIC can reduce the control memory width by 34.2% on average compared with a heuristic compatibility class algorithm.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_5_901/_p
Copier
@ARTICLE{e83-a_5_901,
author={Young-doo CHOI, In-Cheol PARK, Chong-Min KYUNG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={CLASSIC: An O(n2)-Heuristic Algorithm for Microcode Bit Optimization Based on Incompleteness Relations},
year={2000},
volume={E83-A},
number={5},
pages={901-908},
abstract={This paper presents a heuristic algorithm called CLASSIC for the minimization of the control memory width in microprogrammed processors or the instruction memory width of application-specific VLIW (Very Long Instruction Word) processors. CLASSIC results in nearly optimal solutions with the time complexity of O(n2), where n denotes the number of microoperations. In this paper, we also propose the so-called incompleteness relations which are exploited for the minimization of the control memory width. Experiments using various examples have shown that CLASSIC always achieves smaller microprogram widths compared to the earlier techniques based on the maximal compatibility class or the minimal AND/OR set. The results show that CLASSIC can reduce the control memory width by 34.2% on average compared with a heuristic compatibility class algorithm.},
keywords={},
doi={},
ISSN={},
month={May},}
Copier
TY - JOUR
TI - CLASSIC: An O(n2)-Heuristic Algorithm for Microcode Bit Optimization Based on Incompleteness Relations
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 901
EP - 908
AU - Young-doo CHOI
AU - In-Cheol PARK
AU - Chong-Min KYUNG
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2000
AB - This paper presents a heuristic algorithm called CLASSIC for the minimization of the control memory width in microprogrammed processors or the instruction memory width of application-specific VLIW (Very Long Instruction Word) processors. CLASSIC results in nearly optimal solutions with the time complexity of O(n2), where n denotes the number of microoperations. In this paper, we also propose the so-called incompleteness relations which are exploited for the minimization of the control memory width. Experiments using various examples have shown that CLASSIC always achieves smaller microprogram widths compared to the earlier techniques based on the maximal compatibility class or the minimal AND/OR set. The results show that CLASSIC can reduce the control memory width by 34.2% on average compared with a heuristic compatibility class algorithm.
ER -