New Evolutionary Techniques for Test-Program
                                                                                        Generation for Complex Microprocessor Cores
                                                                     E. Sanchez, M. Schillaci, M. Sonza Reorda, G. Squillero, L. Sterpone, M. Violante
                                                                                   Politecnico di Torino - Dip. Automatica e Informatica
                                                                                                 Cso Duca degli Abruzzi 24
                                                                                                    10129 Torino – Italy
                                                                                                      +39 011 5647092
                                                                        { sanchez, schillaci, sonza, squillero, sterpone, violante } @cad.polito.it

ABSTRACT Checking if microprocessor cores are fully functional at the end of Techniques without feedback are essentially pseudo-random the productive process has become a major issue. Traditional approaches able to generate random sequences of instructions functional approaches are not sufficient when considering modern fitting some specific constraints. This kind of methodologies has designs. This paper describes new improvements for an existing been broadly investigated, for instance in [2, 3, 4]. Feedback- evolutionary algorithm, called μGP, able to generate Turing- based generators, on the other hand, are usually far more effective, complete programs; these are exploited, along with hardware but their computational complexity usually prevents the acceleration techniques, to add content to a qualifying test exploitation of such methodologies even against medium-sized campaign by automatically generating assembly programs. The microprocessors. approach is suitable for medium-sized processor cores. The Stemming from [5], [6] describes a feedback-based approach experimental evaluation performed on a SPARCv8 clearly shows called μGP. The μGP is an evolutionary approach for generating the potentiality of the approach, and the effectiveness of the assembly programs tuned for a specific microprocessor. Even enhancements to the evolutionary core. though the evolutionary core has been improved to increase its Categories and Subject Descriptors performance, until now the number of evaluations required in the D.1.m [Programming Techniques]: Miscellaneous evolution has prevented the μGP from tackling testability on medium-sized microprocessors. For example, assessing the General Terms effectiveness of one test program would require several days on a Algorithms workstation. Keywords 2.PROPOSED APPROACH Evolutionary algorithms, Automatic test program generation. Being based on the μGP, the proposed methodology can be classified as feedback based; it additionally exploits hardware 1.INTRODUCTION acceleration techniques. After production, any new microprocessor must be checked by The basic idea behind our hardware acceleration consists in means of a post-production test, to ensure that it is fully instrumenting the target microprocessor core to measure its functional. Production yield is relatively low, so test is one of the internal activity, and to perform fault simulation. Finally, the biggest issues in delivering a high performance device today [1]. design is mapped on a FPGA-based device that emulates the core The new evolutionary improvements are verified against a real during program execution [7]. problem such as pipeline testability for a medium-sized The original μGP is described in [6], so only the latest microprocessor core. The task is to automatically add content to a improvements to the method are described here and will be test suite for a qualifying test campaign. The proposed approach detailed below. focuses on a hard-to-test structure, not easily addressed by the For this work, self-adaptation of the tournament size for traditional functional techniques. tournament selection has been added to the core, making it an Methods for automatically generating test programs may be endogenous parameter. The tournament size is increased when the classified either as “with feedback” or “without feedback”. tool is able to obtain significant fitness improvements and it is decreased when gains are small or nonexistent. The purpose of the second upgrade to the tool, a local mutation operator, is to perform an efficient search of the nearby solution space around a high-fitness individual, thereby enabling faster exploitation of the local maximums. The latest additions to the tool’s capabilities are the aging of the individuals and the user option of choosing the elite population size, defined here as the number of individuals that are not Copyright is held by the author/owner(s). affected by aging. The original core implements a distinctly elitist GECCO’05, June 25-29, 2005, Washington, DC, USA. scheme. This may perform poorly on some class of problems. ACM 1-59593-010-8/05/0006. Since the μGP tool is meant to be useable for generic problem

                                                            2193

solving, it makes sense to allow it to use either an elitist scheme or contrary to expectations, the evolutionary process exactly follows a non-elitist one. the original one. Tournament size self-adaptation allows the tool 3.CASE STUDY to avoid getting stuck in a local optimum, so the Tau experiment The proposed approach was tested on a SPARCv8: a gives better results than the simple elitism relaxation. synthesizable VHDL model of a 32-bit microprocessor 100.00% conforming to the IEEE-1754 architecture [8]. The 99.50% microprocessor pipeline is organized in 5 stages: fetch, decode, execute, memory and write back. The netlist resulting from 99.00% synthesis numbers about 65,000 gates (without the cache). 98.50% An initial test set was carefully written according to the method 98.00% proposed in [9]. Although it is effective, on some parts of the microprocessor the approach is not sufficient. More specifically, 97.50% 40% of the stuck-at faults in the 742 flip-flops composing the 97.00% pipeline registers were not detected by the initial test set. A 0 500 1000 1500 2000 2500 prototype of the proposed approach was built tackling such faults. Reference Loc Tau Age Complete The hardware accelerator exploits an FPGA board equipped with a Virtex 2000E device. The whole process takes about 26 hours to Figure 1 - Result summary complete. For comparison, a random test set has been evaluated. Table 1 summarizes the results. Fault coverage refers to the faults 4.CONCLUSIONS in the pipeline registers. The paper presents a novel approach for the automatic completion Table 1. Fault Coverage Results of a test suite for a medium-sized microprocessor core. The Test Set Fault Clock Instructions technique has been tested on the SPARCv8 as a case study, and Coverage [%] Cycles [#] [#] experimental results clearly show its effectiveness improving the traditional approach. Traditional 58.89 11,263 286 The proposed approach introduces different enhancements in Completed 100.00 15,843 402 μGP, an existing evolutionary algorithm for generating assembly- Rnd_Comp 78.23 12,589 341 language programs, and exploits a hardware accelerator to efficiently evaluate individuals. The experimental evaluation Remarkably, the proposed method is able to improve a typical set shows their usefulness in the specific task. of test programs composed of random programs or deterministic 5.REFERENCES ones by better tackling internal complex structures such as the processor pipeline. [1] International Technology Roadmap for Semiconductors, Five experiments were performed to evaluate the effect of the [2] 2003 edition proposed improvements to the evolutionary core. The first one has K. Batcher, C. Papachristou, “Instruction Randomization been performed using the previous version of the evolutionary Self Test For Processor Cores”, IEEE VLSI Test Symposium, core, and is called the Reference. Three experiments were made to 1999, pp. 34-40 isolate the effects of every single improvement to the tool, and are [3] L. Chen, S. Dey, “DEFUSE: A Deterministic Functional indicated by Age, Loc and Tau. The final one has been performed Self-Test Methodology for Processors”, IEEE VLSI Test implementing all of the improvements in the μGP core, and is Symposium, 2000, pp. 255-262 shown under the name Complete. All of these experiments use the [4] P. Parvathala, K. Maneparambil, W. Lindsay, “FRITS — a same evolutionary parameters. The features employed in the five Microprocessor Functional Bist Method”, International Test experiments are shown in Table 2. Conference, 2002, pp. 590-598 Table 2. Experimental Setup [5] F. Corno, G. Cumani, M. Sonza Reorda, G. Squillero, Experiment Elitism Tournament size Local “Fully Automatic Test Program Generation for self-adaptation search Microprocessor Cores”, IEEE Design, Automation and Test Reference strong no no in Europe, 2003, pp. 1006-1011 Age relaxed no no [6] G. Squillero, “MicroGP — An Evolutionary Assembly Loc strong no yes Program Generator”, to appear on: Genetic Programming Tau strong yes no and Evolvable Machines, 2005 Complete relaxed yes yes [7] Jin-Hua Hong, Shih-Arn Hwang, Cheng-Wen Wu, “An FPGA-based hardware emulator for fast fault emulation”, Figure 1 reports the best fitness at every generation in all the IEEE 39th Midwest Symposium on, Volume: 1, 18-21 Aug. experiments. [8] 1996, pp. 345-348 val.1 The Loc experiment, exploiting local mutation, even performs [9] SPARC International, The SPARC Architecture Manual worse than the original evolutionary process. This is a sure sign N. Kranitis, G. Xenoulis, A. Paschalis, D. Gizopoulos, Y. that the fitness function is a deceptive one. The Age experiment, Zorian, “Application and Analysis of RT-Level Software- which employs individual aging, greatly relaxes the elitist scheme, Based Self-Testing for Embedded Processor Cores”, allowing greater freedom in the solutions space search. But, International Test Conference, 2003, pp. 431-440

                                                                     2194