Abstract
In this article we propose two novel methods to improve the testability of the designs produced by high-level synthesis tools. Our first method, loop-breaking algorithm, identifies self-loops in a design generated by a high-level synthesis system and eliminates as many of these loops as possible by altering the register and module bindings. The second method, BINET with test cost, is a binding algorithm that takes the cost of testing into account during the binding phase of the high-level synthesis. The test cost considered in this article is a function of the number of self-loops in the synthesized design. Thus it generates only those solutions that have fewer if any self-loops. Finally we put the two methods together in which we first use BINET with test cost to produce nearly self-loop free designs and we further improve their testability by using the loop-breaking algorithm. We applied these methods to synthesis benchmark circuits and the results of our study, given in this article, show that the designs produced by our method have indeed reduced testability overhead and improved testability.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M.C. McFarland, A.C. Parker, and R. Camposano, “The High-Level Synthesis of Digital Systems,”Proc. of the IEEE, vol. 78, pp. 301–318, Feb. 1990.
B.M. Pangrle, “On the complexity of connectivity binding,”IEEE Trans. on Computer-Aided Design, vol. 10, pp. 1460–1465, Nov. 1990.
V.D. Agrawal, K.T. Cheng, D.D. Johanson, and T. Lin, “A Complete Solution to the Partial Scan Problem,”Proc. of the International Test Conf., pp. 44–51, Sept. 1987.
R. Gupta, R. Gupta, and M.A. Breuer, “The ballast methodology for structured partial scan design,”IEEE Trans. on Computers, vol. 39, pp. 538–544, April 1990.
A. Kunzmann and H.-J. Wunderlich, “An analytical approach to the partial scan problem,”Journal of Electronic Testing: Theory and Applications, vol. 1, pp. 163–174, May 1990.
J.W. Lee, Automatic Synthesis of Testable Designs. Master's Report, Department of Electrical and Computer Engineering, University of Wisconsin-Madison, May 1991.
L. Avra, “Allocation and Assignment in High-Level Synthesis for Self-Testable Data Paths,”Proc. of the 1991 International Test Conf., pp. 463–472, Oct. 1991.
C.H. Gebotys and M.I. Elmasry, “Integration of algorithmic VLSI synthesis with testability incorporation,”IEEE Journal of Solid-State Circuits, vol. 24, pp. 409–416, April 1989.
C. Papachristou, S. Chiu, and H. Harmanani, “A Data Path Synthesis Method for Self-Testable Designs,”Proc. of the 28th Design Automation Conf., pp. 378–384, June 1991.
T-C. Lee, W.H. Wolf, N.K. Jha, and J.M. Acken, Behavioral Synthesis for Easy Testability in Data Path Allocation,Proc. of the International Conf. on Computer Design, pp. 29–32, Oct. 1992.
V.D. Agrawal, S.K. Jain, and D.M. Singer, “Automation in Design for Testability,”Proc. of Custom Integrated Circuits Conf., pp. 159–163, May 1984.
K.-T. Cheng and V.D. Agrawal, “A partial scan method for sequential circuits with feedback,”IEEE Trans. on Computers, vol. 39, pp. 544–548, April 1990.
R. Gupta,Advanced Serial Scan Design for Testability, Ph.D. thesis, Department of Electrical and Computer Engineering, University of Southern California, February 1991.
M. Rim, R. Jain, and R. De Leone, “Optimal Allocation and Binding in High-Level Synthesis,”Proc. of the 29th Design Automation Conf., pp. 120–123, June 1992.
N. Park and F.J. Kurdahi, “Module Assignment and Interconnect Sharing in Register-Transer Synthesis of Pipelined Designs,”Proc. of the Internationhal Conf. on Computer-Aided Design, pp. 16–19, Nov. 1989.
P.G. Paulin and J.P. Knight, “Force-directed scheduling for the behavioral synthesis of ASICs,”IEEE Trans. on Computer-Aided Design, vol. 8, pp. 661–679, June 1989.
C.J. Tseng and D.P. Siewiorek, “Automated synthesis of data paths in digital systems,”IEEE Trans. on Computer-Aided Design, vol. 5, pp. 379–395, July 1986.
B.W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,”The Bell System Technical Journal, vol. 49, pp. 291–307, 1970.
K. Kucukcakar and A.C. Parker, “Data Path Trade-offs Using MABAL,”Proc. of the 27th Design Automation Conf., pp. 511–516, June 1990.
M.C. McFarland, “Allocating Registers, Processors, and Connections,” Technical report, Department of Electrical Engineering, Carnegie-Mellon Univesity, August 1981.
J.P. Weng and A.C. Parker, “3D Scheduling: High-Level Synthesis with Floorplanning,”Proc. of the 29th Design Automation Conf., pp. 668–673, June 1991.
D. Bertsekas,Linear Network Optimization, The MIT Press, Cambridge, MA, 1991.
R. Jain, A. Mujumdar, A. Sharma, and H. Wang, “Experimental Evaluation of Some High-Level Synthesis Scheduling Heuristics,”Proceedings of the 28th Design Automation Conf., pp. 686–689, June 1991.
T.P. Kelsey, K.K. Saluja, and S.Y. Lee, “An efficient algorithm for sequential circuit test generation,IEEE Trans. on Computers, vol. 42, pp. 1361–1371, Nov. 1993.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mujumdar, A., Jain, R. & Saluja, K. Incorporating testability considerations in high-level synthesis. J Electron Test 5, 43–55 (1994). https://doi.org/10.1007/BF00971962
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00971962