Cited By
View all- Ibrahim AIbrahim AEl-Kharashi MSafar M(2023)Adaptive SAT Modeling for Optimal Pattern Retargeting in IEEE 1687 NetworksIEEE Transactions on Computers10.1109/TC.2023.333619873:2(536-547)Online publication date: 1-Dec-2023
Optimal Pattern Retargeting in IEEE 1687 Networks: A SAT-based Upper-Bound Computation
Authors: 
Abrar A. Ibrahim, Ahmed M. Y. Ibrahim, Mohamed Watheq El-Kharashi, Mona SafarAuthors Info & Claims
Article No.: 62, Pages 1 - 26
Abstract
A growing number of embedded instruments is being integrated into System-on-Chips for testing, monitoring, and several other purposes. To standardize their access protocols, the IEEE 1687 (IJTAG) standard has defined a flexible network infrastructure. Finding the shortest path in such networks requires a comprehensive search over a solution space, bounded by a limited number of time frames. This bound must be selected carefully, as it can neither be too large (to avoid unnecessary long execution time) nor too small (to avoid missing the optimal solution). Previous work was not efficiently applicable to all segments of IJTAG networks, with some providing unrealistic bounds and others having scope limitations or scalability issues. In this work, we present a new methodology for computing the upper-bound on the number of time frames using the Boolean Satisfiability Problem (SAT). Our proposed technique can also be customized to perfectly adapt to instruments access procedures, which in turn increases efficiency by reducing the time spent searching for required configurations. Results show the effectiveness of our work in computing the upper-bound for irregular benchmarks that are not constrained by a specific network design. This is achieved with a controlled increase in execution time, in contrast to previous work.
References
[1]
2013. IEEE standard for test access port and boundary-scan architecture. IEEE Std 1149.1-2013 (Revision of IEEE Std 1149.1-2001) (May2013), 1–444.
[2]
2014. IEEE standard for access and control of instrumentation embedded within a semiconductor device. IEEE Std 1687-2014 (Dec.2014), 1–283.
[3]
Ghazanfar Ali, Ahmed Badawy, and Hans G. Kerkhoff. 2016. Accessing on-chip temperature health monitors using the IEEE 1687 standard. In 2016 IEEE International Conference on Electronics, Circuits and Systems (ICECS) (2016-12). IEEE, Monte Carlo, Monaco, 776–779.
[4]
Rafal Baranowski, Michael A. Kochte, and Hans-Joachim Wunderlich. 2012. Modeling, verification and pattern generation for reconfigurable scan networks. In 2012 IEEE International Test Conference (ITC) (2012-11). IEEE, Anaheim, CA, USA, 1–9.
[5]
Rafal Baranowski, Michael A. Kochte, and Hans-Joachim Wunderlich. 2013. Scan pattern retargeting and merging with reduced access time. In 2013 18TH IEEE European Test Symposium (ETS) (2013-05). IEEE, Avignon, France, 1–7.
[6]
Niklas Eén and Niklas Sörensson. 2003. Temporal induction by incremental SAT solving. Electronic Notes in Theoretical Computer Science 89, 4 (2003), 543–560. Issue 4.
[7]
Niklas Eén and Niklas Sörensson. 2004. An extensible SAT-solver. In Theory and Applications of Satisfiability Testing (SAT 2003), Enrico Giunchiglia and Armando Tacchella (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 502–518.
[8]
Niklas Eén and Niklas Sörensson. 2006. Translating pseudo-boolean constraints into SAT. Journal on Satisfiability, Boolean Modeling and Computation 2 (2006), 1–26.
[9]
Ahmed M. Y. Ibrahim and Hans G. Kerkhoff. 2014. iJTAG integration of complex digital embedded instruments. In 2014 9th International Design and Test Symposium (IDT) (2014-12). IEEE, Algeries, Algeria, 18–23.
[10]
Ahmed M. Y. Ibrahim and Hans G. Kerkhoff. 2016. Analysis and design of an on-chip retargeting engine for IEEE 1687 networks. In 2016 21th IEEE European Test Symposium (ETS) (2016-05). IEEE, Amsterdam, Netherlands, 1–6.
[11]
Ahmed M. Y. Ibrahim and Hans G. Kerkhoff. 2019. An on-chip IEEE 1687 network controller for reliability and functional safety management of system-on-chips. In 2019 IEEE International Test Conference in Asia (ITC-Asia) (2019-09). IEEE, Tokyo, Japan, 109–114.
[12]
Ahmed M. Y. Ibrahim, Hans G. Kerkhoff, Abrar Ibrahim, Mona Safar, and Mohamed W. El-Kharashi. 2019. Efficient structured scan patterns retargeting for hierarchical IEEE 1687 networks. In 2019 IEEE 37th VLSI Test Symposium (VTS) (2019-04). IEEE, Monterey, CA, USA, 1–6.
[13]
Artur Jutman, Sergei Devadze, and Konstantin Shibin. 2013. Effective scalable IEEE 1687 instrumentation network for fault management. IEEE Design Test 30, 5 (Oct.2013), 26–35. Issue 5.
[14]
Rene Krenz-Baath, Farrokh G. Zadegan, and Erik Larsson. 2015. Access time minimization in IEEE 1687 networks. In 2015 IEEE International Test Conference (ITC) (2015-10). IEEE, Anaheim, CA, USA, 1–10.
[15]
Sharad Malik and Georg Weissenbacher. 2012. Boolean satisfiability solvers: Techniques and extensions. NATO Science for Peace and Security Series, D: Information and Communication Security 33, Software Safety and Security (2012), 205–253.
[16]
Erik J. Marinissen, Vikram Iyengar, and Krishnendu Chakrabarty. 2002. A set of benchmarks for modular testing of SOCs. In Proceedings. International Test Conference. IEEE, Baltimore, MD, USA, 519–528.
[17]
Michela Milano and Andrea Roli. 2000. Solving the satisfiability problem through boolean networks. In Advances in Artificial Intelligence 6th Congress of Italian Association for Artificial Intelligence(AI*IA 99) (2000), Evelina Lamma and Paola Mello (Eds.). Springer Berlin Heidelberg, Bologna, Italy, 72–83.
[18]
Jeff Rearick, Bill Eklow, Ken Posse, Alfred L. Crouch, and Ben Bennetts. 2005. IJTAG (internal JTAG): A step toward a DFT standard. In 2005 IEEE International Test Conference (ITC). IEEE, Austin, TX, USA, 8 pp.–815.
[19]
Anton Tšertov, Artur Jutman, Sergei Devadze, Matteo S. Reorda, Erik Larsson, Farrokh G. Zadegan, Riccardo Cantoro, Mehrdad Montazeri, and Rene Krenz-Baath. 2016. A suite of IEEE 1687 benchmark networks. In 2016 IEEE International Test Conference (ITC) (2016-11). IEEE, Fort Worth, TX, USA, 1–10.
[20]
Farrokh G. Zadegan, Urban Ingelsson, Gunnar Carlsson, and Erik Larsson. 2011. Design automation for IEEE P1687. In 2011 Design, Automation & Test in Europe (2011-03). IEEE, Grenoble, France, 1–6.
[21]
Farrokh G. Zadegan, Rene Krenz-Baath, and Erik Larsson. 2016. Upper-bound computation for optimal retargeting in IEEE1687 networks. In 2016 IEEE International Test Conference (ITC) (2016-11). IEEE, Fort Worth, TX, USA, 1–10.
[22]
Farrokh G. Zadegan, Erik Larsson, Artur Jutman, Sergei Devadze, and Rene Krenz-Baath. 2014. Design, verification, and application of IEEE 1687. In 2014 IEEE 23rd Asian Test Symposium (ATS) (2014-11). IEEE, Hangzhou, China, 93–100.
Index Terms
- Optimal Pattern Retargeting in IEEE 1687 Networks: A SAT-based Upper-Bound Computation
Recommendations
Incremental solving techniques for SAT-based ATPG
Automatic test pattern generation (ATPG) based on the Boolean satisfiability (SAT) problem has recently been proven to be a beneficial complement to traditional methods. Efficient SAT techniques yield a robust fault classification. In this paper, we ...
Accessing Embedded DfT Instruments with IEEE P1687
ATS '12: Proceedings of the 2012 IEEE 21st Asian Test SymposiumWhile the advancement in semiconductor technologies enables manufacturing of highly advanced and complex integrated circuits, there is an increasing need of embedded (on-chip) instruments for test, debug, diagnosis, configuration, monitoring, etc. A key ...
On Acceleration of SAT-Based ATPG for Industrial Designs
Due to the rapidly growing size of integrated circuits, there is a need for new algorithms for automatic test pattern generation (ATPG). While classical algorithms reach their limit, there have been recent advances in algorithms to solve Boolean ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
432 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 17 May 2023
Online AM: 27 February 2023
Accepted: 06 February 2023
Revised: 13 January 2023
Received: 19 August 2022
Published in TODAES Volume 28, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 104Total Downloads
- Downloads (Last 12 months)29
- Downloads (Last 6 weeks)5
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
Cited By
View all- Ibrahim AIbrahim AEl-Kharashi MSafar M(2023)Adaptive SAT Modeling for Optimal Pattern Retargeting in IEEE 1687 NetworksIEEE Transactions on Computers10.1109/TC.2023.333619873:2(536-547)Online publication date: 1-Dec-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in