Article

SoC test scheduling using the B-tree based floorplanning technique

Authors:

Jen-Yi Wuu,

Tung-Chieh Chen,

Yao-Wen ChangAuthors Info & Claims

ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference

Pages 1188 - 1191

https://doi.org/10.1145/1120725.1120937

Published: 18 January 2005 Publication History

Get Access

Abstract

We present in this paper a new algorithm to co-optimize the problems of test scheduling and core wrapper design under power constraints for core-based SoC (System on Chip) designs. The problem of test scheduling is first transformed into a floorplanning problem with a given maximum height (test access mechanism width) constraint. Then, we apply the B*-tree based floorplanning technique to solve the SoC test scheduling problem. Experimental results based on the ITC'02 benchmarks show that our method is very effective and efficient---our method obtains the best results ever reported for SoC test scheduling with power constraint in every efficient running time. Compared with recent works, our method achieves average improvements of 4.7% to 20.1%.

References

[1]

V. Iyengar, K. Chakrabarty, and E. J. Marinissen, "On using rectangle packing for SOC wrapper/TAM co-optimization," VTS, pp.253--258, 2002.

Digital Library

Google Scholar

[2]

K. Chakrabarty, "Test scheduling for core-based system using mixed-integer linear programming," IEEE TCAD, pp.1163--1174, 2000.

Digital Library

Google Scholar

[3]

V. Iyengar, K. Chakrabarty, and E. J. Marinissen, "Test wrapper and test access mechanism co-optimization for System-on-Chip," ITC, pp.1023--1032, 2001.

Digital Library

Google Scholar

[4]

Y. Huang, S. M. Reddy, W.-T. Cheng, and P. Reuter, "Optimal core wrapper width selection and SOC test scheduling based on 3-D bin packing algorithm," ITC, pp.74--82, 2002.

Digital Library

Google Scholar

[5]

W. Zou, S. M. Reddy, I. Pomeranz, and Y. Huang, "SOC test scheduling using simulated annealing," VTS, 2003.

Digital Library

Google Scholar

[6]

Y. Xia, M. Chrzanowska-Jeske, B. Wang, and M. Jeske, "Using a distributed rectangle bin-packing approach for core-based SoC test scheduling with power constraints," ICCAD, pp.100--105, 2003.

Digital Library

Google Scholar

[7]

Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, "B*-Trees: A new representation for non-slicing floorplans," DAC, pp.458--463, 2000.

Digital Library

Google Scholar

[8]

Y. Zorian, E. J. Marinissen, and S. Dey, "Testing embedded core-based system chips," ITC, pp. 130--143, 1998.

Digital Library

Google Scholar

[9]

S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, "Optimization by simulated annealing," pp.671--680, Science, Vol.220, No.4598, 1983.

Google Scholar

[10]

E. J. Marinissen, V. Iyengar, and K. Chakrabarty. ITC'02 SoC Test Benchmarks, http://www.extra.research.philips.com/itc02socbenchm/

Google Scholar

[11]

P.-N. Guo, C.-K. Cheng, and T. Yoshimura, "An O-Tree representation of non-slicing floorplan and its application," DAC, pp.268--273, 1999.

Digital Library

Google Scholar

Cited By

View all

Karmakar RChattopadhyay S(2018)Window-based peak power model and Particle Swarm Optimization guided 3-dimensional bin packing for SoC test schedulingIntegration, the VLSI Journal10.1016/j.vlsi.2015.01.00650:C(61-73)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1016/j.vlsi.2015.01.006
Ooi CSua JLee S(2018)Power-aware system-on-chip test scheduling using enhanced rectangle packing algorithmComputers and Electrical Engineering10.1016/j.compeleceng.2012.04.01038:6(1444-1455)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1016/j.compeleceng.2012.04.010
Marrouche WFarah RHarmanani H(2017)A Multiobjective Optimization Method for the SOC Test Time, TAM, and Power Optimization Using a Strength Pareto Evolutionary AlgorithmInformation Technology - New Generations10.1007/978-3-319-54978-1_86(685-695)Online publication date: 18-Jul-2017
https://doi.org/10.1007/978-3-319-54978-1_86
Show More Cited By

SoC test scheduling using the B-tree based floorplanning technique
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Modern floorplanning based on B^*-tree and fast simulated annealing

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern very large scale integration (VLSI) floorplanning typically needs to pack blocks within a fixed die (outline), and additionally considers the packing ...
Modern floorplanning based on fast simulated annealing
ISPD '05: Proceedings of the 2005 international symposium on Physical design

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern VLSI floorplanning typically needs to pack blocks within a fixed die (outline) and additionally considers the packing with block positions and ...
DELAY BOUNDED BUFFERED TREE CONSTRUCTION FOR TIMING DRIVEN FLOORPLANNING

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference

January 2005

1495 pages

ISBN:0780387376

DOI:10.1145/1120725

General Chair:
Ting-Ao Tang
Fudan University, Shanghai, P. R. China

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 ACM 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

Publication History

Published: 18 January 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ASPDAC05

Sponsor:

SIGDA

ASPDAC05: Asia and South Pacific Design Automation Conference

January 18 - 21, 2005

Shanghai, China

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
184
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Karmakar RChattopadhyay S(2018)Window-based peak power model and Particle Swarm Optimization guided 3-dimensional bin packing for SoC test schedulingIntegration, the VLSI Journal10.1016/j.vlsi.2015.01.00650:C(61-73)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1016/j.vlsi.2015.01.006
Ooi CSua JLee S(2018)Power-aware system-on-chip test scheduling using enhanced rectangle packing algorithmComputers and Electrical Engineering10.1016/j.compeleceng.2012.04.01038:6(1444-1455)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1016/j.compeleceng.2012.04.010
Marrouche WFarah RHarmanani H(2017)A Multiobjective Optimization Method for the SOC Test Time, TAM, and Power Optimization Using a Strength Pareto Evolutionary AlgorithmInformation Technology - New Generations10.1007/978-3-319-54978-1_86(685-695)Online publication date: 18-Jul-2017
https://doi.org/10.1007/978-3-319-54978-1_86
Giri CSarkar SChattopadhyay S(2009)Test Scheduling for Core-Based SOCs Using Genetic Algorithm Based Heuristic ApproachProceedings of the 3rd International Conference on Intelligent Computing: Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence10.1007/978-3-540-74205-0_107(1032-1041)Online publication date: 17-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-540-74205-0_107
Jinyu ZXunsheng LBing GGuangze XNan S(2008)A Test Scheduling Scheme for Core-Based SoCs Using Genetic Algorithm2008 International Conference on Embedded Software and Systems Symposia10.1109/ICESS.Symposia.2008.65(38-43)Online publication date: Jul-2008
https://doi.org/10.1109/ICESS.Symposia.2008.65
Yuh PYang CChang Y(2007)Placement of defect-tolerant digital microfluidic biochips using the T-tree formulationACM Journal on Emerging Technologies in Computing Systems (JETC)10.1145/1295231.12952343:3(13-es)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1145/1295231.1295234
Giri CSarkar SChattopadhyay S(2007)A genetic algorithm based heuristic technique for power constrained test scheduling in core-based SOCs2007 IFIP International Conference on Very Large Scale Integration10.1109/VLSISOC.2007.4402522(320-323)Online publication date: Oct-2007
https://doi.org/10.1109/VLSISOC.2007.4402522
Giri CTipparthi DChattopadhyay S(2007)Genetic Algorithm Based Approach for Hierarchical SOC Test SchedulingProceedings of the International Conference on Computing: Theory and Applications10.1109/ICCTA.2007.65(141-145)Online publication date: 5-Mar-2007
https://dl.acm.org/doi/10.1109/ICCTA.2007.65

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Modern floorplanning based on B^*-tree and fast simulated annealing

Modern floorplanning based on fast simulated annealing

DELAY BOUNDED BUFFERED TREE CONSTRUCTION FOR TIMING DRIVEN FLOORPLANNING