NoC-Based SoC Test Scheduling Using Ant Colony Optimization

ETRI Journal

关键词: ant colony optimization;    rectangle packing;    NoC-based SoC test scheduling;   

Others  :  1185723
DOI  :  10.4218/etrij.08.0107.0090

【 摘 要 】

In this paper, we propose a novel ant colony optimization (ACO)-based test scheduling method for testing network-on-chip (NoC)-based systems-on-chip (SoCs), on the assumption that the test platform, including specific methods and configurations such as test packet routing, generation, and absorption, is installed. The ACO metaheuristic model, inspired by the ant’s foraging behavior, can autonomously find better results by exploring more solution space. The proposed method efficiently combines the rectangle packing method with ACO and improves the scheduling results by dynamically choosing the test-access-mechanism widths for cores and changing the testing orders. The power dissipation and variable test clock mode are also considered. Experimental results using ITC’02 benchmark circuits show that the proposed algorithm can efficiently reduce overall test time. Moreover, the computation time of the algorithm is less than a few seconds in most cases.

   

【 参考文献 】

• [1]L. Benini and G.D. Micheli, "Networks on Chips: A New SoC Paradigm," IEEE Computer, vol. 35, Jan. 2002, pp. 70-78.
• [2]A. Ivanov and G.D. Micheli, "The Network-on-Chip Paradigm in Practice and Research," IEEE Design&Test of Computers, Sept./Oct. 2005, pp. 399-403.
• [3]J.-H. Ahn and S. Kang, "Test Scheduling of NoC-based SoCs Using Multiple Test Clocks," ETRI Journal, vol. 28, no. 4, Aug. 2006, pp. 475-485.
• [4]V. Iyengar, K. Chakrabarty, and E.J. Marinissen, "On Using Rectangle Packing for SOC Wrapper/TAM Co-Optimization," Proc. VTS, 2002, pp. 253-258.
• [5]B. Vermeulen, J. Dielissen, K. Goossens, and C. Ciordas, "Bringing Communication Networks on a Chip: Test and Verification Implications," IEEE Communications Magazine, vol. 41, Sept. 2003, pp. 74-81.
• [6]P.P. Pande, G.D. Micheli, C. Grecu, A. Ivanov, and R. Saleh, "Design, Synthesis, and Test of Networks on Chips," IEEE Design&Test of Computers, Sept./Oct. 2005, pp. 404-413.
• [7]A.M. Amory, E. Briao, E. Cota, M. Lubaszewski, and F.G. Moraes, "A Scalable Test Strategy for Network-on-Chip Routers," Proc. ITC, Nov. 2005, pp. 591-599.
• [8]C. Grecu, P. Pande, B. Wang, A. Ivanov, and R. Saleh, "Methodologies and Algorithms for Testing Switch-Based NoC Interconnects," Proc. DFT, Oct. 2005, pp. 238-246.
• [9]X.-T. Tran, J. Durupt, F. Bertrand, V. Beroulle, and C. Robach, "A DFT Architecture for Asynchronous Networks-on-Chip," Proc. ETS, May 2006, pp. 219-224.
• [10]A.M. Amory, K. Goossens, E.J. Marinissen, M. Lubaszewski, and F. Moraes, "Wrapper Design for the Reuse of Networks-on-Chip as Test Access Mechanism," May 2006, Proc. ETS, pp. 213-218.
• [11]M. Nahvi and A. Ivanov, "Indirect Test Architecture for SoC Testing," IEEE Trans. on CAD, vol. 23, no. 7, July 2004, pp. 1128-1142.
• [12]E. Cota, M. Kreutz, C.A. Zeferino, L. Carro, M. Lubaszewski, and A. Susin, "The Impact of NoC Reuse on the Testing of Core-Based Systems," Proc. VTS, Apr. 2003, pp. 128-133.
• [13]E. Cota, L. Carro, F. Wagner, and M. Lubaszewski, "Power-Aware NoC Reuse on the Testing of Core-Based Systems," Proc. ITC, vol. 1, Sept. 2003, pp. 612-621.
• [14]C. Liu, E. Cota, H. Sharif, and D.K. Pradhan, "Test Scheduling for Network-on-Chip with BIST and Precedence Constraints," Proc. ITC, Oct. 2004, pp. 1369-1378.
• [15]C. Liu, V. Iyengar, J. Shi, and E. Cota, "Power-Aware Test Scheduling in Network-on-Chip Using Variable-Rate On-Chip Clocking," Proc. VTS, May 2005, pp. 349-354.
• [16]C. Liu, Z. Link, and D.K. Pradhan, "Reuse-Based Test Access and Integrated Test Scheduling for Network-on-Chip," Proc. DATE, 2006.
• [17]C. Liu, V. Iyengar, and D.K. Pradhan, "Thermal-Aware Testing of Network-on-Chip Using Multiple-Frequency Clocking," Proc. VTS, Apr. 2006, pp. 46-51.
• [18]Y. Huang, W.-T. Cheng, C.-C. Tsai, N. Mukherjee, O. Samman, Y. Zaidan, and S.M. Reddy, "Resource Allocation and Test Scheduling for Concurrent Test of Core-Based SOC Design," Proc. ATS, 2001, pp. 265-270.
• [19]Y. Huang, S.M. Reddy, W.-T. Cheng, P. Reuter, N. Mukherjee, C.-C. Tsai, O. Samman, and Y. Zaidan, "Optimal Core Wrapper Width Selection and SOC Test Scheduling Based on 3-D Bin Packing Algorithm," Proc. ITC, 2002, pp. 74-82.
• [20]E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence from Natural to Artificial Systems, Oxford University Press, 1999.
• [21]M. Dorigo and T. Stuetzle, Ant Colony Optimization, MIT Press, 2004.
• [22]M. Dorigo, M. Zlochin, N. Meuleau, and M. Birattari, "Updating ACO Pheromones Using Stochastic Gradient Ascent and Cross-Entropy Methods," Proc. Evo Workshops, LNCS 2279, 2002, pp. 21-30.
• [23]F. Glover and G. Kochenberger, Handbook of Metaheuristics, Kluwer Academic Publishers, 2003.
• [24]M. Dorigo, V. Maniezzo, and A. Colorni, "The Ant System: Optimization by a Colony of Cooperating Agents," IEEE Trans. on Systems, Man and Cybernetics, Part B, vol. 26, no. 1, 1996, pp. 1-13.
• [25]T. Stutzle and H. Hoos, "MAX-MIN Ant System," Future Generation Computer Systems, vol. 16, no. 8, 2000, pp. 889-914.
• [26]J. Im, S. Chun, G. Kim, J.-H. Ahn, and S. Kang, "RAIN (RAndom INsertion) Scheduling Algorithm for SoC Test," Proc. ATS, Nov. 2004, pp. 242-247.
• [27]J. Levine and F. Ducatelle, "Ant Colony Optimisation and Local Search for Bin Packing and Cutting Stock Problems," Journal of the Operational Research Society, Special Issue on Local Search, vol. 55, no. 7, 2004, pp. 705-716.
• [28]E.J. Marinissen, V. Iyengar and K. Chakrabarty, ITC’02 SoC Test Benchmarks, http://www.hitech-projects.com/itc02socbenchm
• [29]W. Zou, S.M. Reddy, I. Pomeranz, and Y. Huang, "SOC Test Scheduling Using Simulated Annealing," Proc. VTS, 2003, pp. 325-330.