Computer Design A computer aided design and VLSI approach Paul J. Drongowski Chapter 5 - Validating the SP.1 ISA. Once the SP.1 ISA has been captured in a formal specification or simulation program, the ISA must be validated. This chapter concentrates on a testing approach to validation and diagnostic programming is specifically addressed. Section 1 - Intent. The ISA for an architecture presumably embodies the programming features which are required to support one or market segments. The ISA is written by a team of computer architects who try to reflect the concerns and requirements of the potential user community into the technical specification. The collective goals of the design team is called the "intent" of the designers. Some kinds of intent are difficult to quantify. For example, "ease of programming" is subjective motherhood. A programmer's idea of the best machine instruction set may be radically different from those of his colleagues. For such subjective intentions, validation can only be performed around a conference table or through an exchange of technical memorandums. This chapter examines the validation of the ISA model based upon objective, quantifiable criteria. Since the ISA has been written in C language, the validation task is equivalent to either a proof that the program meets its mathematically specification or a demonstration of correctness through testing. The formal verification of an ISA is a research topic and is beyond the scope of this book. Therefore, we will take a testing approach. The reader is reminded that testing will show the presence of bugs rather than their absence and that the thoroughness of the testing procedure will determine the number of bugs remaining in the ISA after test. Section 2 - Controllability and observability. At the ISA level, testing (and validation) is reduced to a software test problem. The test procedure cannot take physical system structure into account for fault isolation as the ISA describes an abstract machine which has not yet been designed. The test problem remains substantial, however, because the ISA simulation program may be quite complicated and have many special features and cases. The SP.1 has only sixteen instructions and is an artificially simple example. The DEC VAX, for example, has 244 basic instructions, fourteen addressing modes, eleven datatypes (byte, word, long word, etc.), and over twenty exceptions. Development and validation of an ISA simulation program for the VAX is an enormous project. That the test procedure has been "reduced" to a software test problem is little comfort to real architects. Software simulation has some advantages, however. First, the controllability and observability of the program is potentially unlimited. The programmer is not restricted to a few I/O pins or connections and the interior state of the simulation is easily observed. Hardware test engineers can only communicate through the few electrical connections that are provided on the chip or board. In the case of VLSI circuits, the interior of the chip cannot be conveniently probed. (Exotic techniques using infrared or electron optics have been developed, but are not in wide-spread use.) The program also be instrumented for performance measurement. Advantages of S/W simulation Input -----> SP.1 -----> Output | | V Exception Figure 1 - SP.1 input and output ports. Section 3 - Test generation. Our goal in this section is to explain techniques for the construction of an ISA diagnostic program for the SP.1 We will use the diagnostic program to validate the ISA and to test the organization and transistor level implementations of the SP.1. The diagnostic program could also serve as a built-in self-test routine which would execute whenever power is applied to the SP.1 or the machine is re-initialized. A diagnostic program must thoroughly test all of the architectural features of the machine. When applied to implementation level testing, the diagnostic program must exercise the machine hardware and possibly isolate faults to specific components. Therefore, a diagnostic program with fault isolation must be constructed with specific knowledge about the structure of the machine implementation. We will include some implementation oriented tests in the example below although our primary task here is ISA validation. The diagnostic program will need to be modified later after the structure of the SP.1 implementation is defined. Our methodology for writing the SP.1 diagnostic program has three strategic characteristics. 1. The program begins testing those instructions which are fundamental to the operation or testing of the more complicated instructions. 2. Some test procedures are carried out externally. An external test apparatus will supply patterns to the program, acquire results and compare the results with expected output values. 3. Test patterns and program data values permit the detection and isolation of s-a-0 and s-a-1 faults. We do not guarantee a high degree of coverage. The design and construction of a comprehensive diagnostic program is left as an exercise. The primary input to the SP.1 is the Input port. The primary outputs of the SP.1 are the Output and Exception ports. During execution of the diagnostic program, test patterns must be provided to the program through the Input port and test results will be acquired from the Output and Exception ports. The program should first check the operation of these ports because they are essential to the rest of the testing process. The Get and Put instructions can be checked by reading and writing a sequence of data values. The instruction sequence, GET /* Get a test value */ PUT /* Put it to the output port */ GET PUT is sufficient to read and write two 8-bit test values. The tester will expect to acquire whatever data value it sent to the SP.1 in response to a Get instruction. If the tester provides the data hexadecimal values "00" and "FF," it will probably detect any s-a-1 or s-a-0 fault through the path from the Input port to the AC register, within AC, or from AC to the Output port. Combinational logic or history sensitive faults may not be uncovered by this test. It may be necessary to toggle AC register bits from 0 to 1 and 1 to 0 twice to reveal a history sensitive fault. To have a high degree of confidence in the Get and Put instructions, they should be checked exhaustively. Exhaustive testing with Get/Put pairs requires 512 bytes of memory. Thus, the small program memory does not permit exhaustive testing without the use of a loop. We prefer not to use a loop (and take a chance on missing faults) as the loop will require the use of untested Immediate, Decrement, and branch instructions. The test code for the Get and Put instructions already makes substantial assumptions about the correct operation of the SP.1. Merely executing two Get/Put pairs will check the following operations. * Reading an instruction byte from program memory. * Instruction decoding. * Advancing the instruction pointer register. * Reading the Input port. * Loading the AC register. * Reading the AC register. * Writing data to the Output port. A fault in any one of these operations will cause the Get/Put sequence to fail. We can see already that although the diagnostic program will be sufficient to validate the ISA, it will not be sufficient to isolate faults in the implementation. The next instruction to be tested should be the Exception instruction. Proper execution of the Exception will give the diagnostic program another reliable channel for reporting test values. The sequence, EXC 0 . . . EXC 15 will exhaustively test the exception port by driving all sixteen 4-bit values through the port. The Exception instruction can then be used to report errors in subsequent tests. Given good Get and Put instructions, the Swap instruction is easy to test. The instruction sequence below will read an external test value into the AC, swap it into the MD register, overwrite the old AC value, swap again, and write the original value to the Output port. GET /* Test value */ SWAP /* Move it to MD */ GET /* Get a different AC value */ SWAP /* Move old test value from MD to AC */ PUT /* Put original test value */ The tester must co-operate by providing two data values and acquiring the result. S-a-0 and s-a-1 faults may be detected by using test values "00" and "FF." A good Swap instruction is needed to test the load Immediate instruction (i.e., for loading MD.) The And instruction is more difficult to test as it conditionally sets the Z flag. The instructions below will get a test value, form the bit-wise AND of that value with a pre-determined mask, set the state of the Z bit and then branch on the expected value of the bit. GET /* Get a test value */ AND 0 /* Set the Z flag */ BRZ 1f /* Branch on Z condition */ EXC 0x1E /* 0x1E is a bad AND test */ 1: The exception code 0x1E signals test failure. Another instruction sequence must be written to check the clearing of the Z flag as well. The And instruction should be exercised with different values to reveal s-a-0 and s-a-1 faults in the AND logic. Fewer external input values will be required if test patterns can be generated and used internally by the diagnostic program. Since the load Immediate instruction provides that capability, it will be checked next. The two instruction sequences, IMMAC value /* Load the AC with a value */ PUT /* Put the value to the output port */ IMMMD value /* Load the MD with a value */ SWAP /* Move MD value to AC */ PUT /* Put the value to the output port */ will test the loading of the AC and MD registers. Values show be chosen to reveal s-a-0 and s-a-1 faults as before. Note that the AC test above does not check the Z flag which should be set to zero. As mentioned before, the conditional branch instruction is the only way that the Z flag can be tested. IMMAC 0 /* Load the AC with zero */ BRZ 1f /* This should always branch */ HALT 0x1F /* Halt and put hex 1F if error */ 1: This sequence will detect a failure to clear the Z flag if the Z flag was initially set. It is also sensitive to errors in the BranchZero instruction and Halt. The Z flag can be forced to one with the instruction, AND 0x00 /* Force the Z flag to one */ which assumes a good And instruction. It is difficult to test the behavior of the CR register because CR cannot be directly transfered to the Output port. Thus, the loading of CR and the Decrement instruction must be checked indirectly with the code given below. IMMCR 255 /* Initialize loop count */ 1: DEC /* Subtract one from CR */ BRZ 2f /* Exit loop on zero */ IMMAC 0 /* Put zeros while in loop */ PUT BR 1b /* Branch back to beginning */ 2: IMMAC 1 /* Put a one when finished */ PUT This loop will put 254 zero values to the Output port followed by a one. S-a-0 and S-a-1 faults in CR should be revealed. We have also assumed that the unconditional branch instruction will operate correctly. The subroutine call and return instructions may be exercised with the following instruction sequence. IMMAC 0 /* Set AC to zero */ CALL 1f /* Call test subroutine */ IMMAC 0xAA /* Output 0xAA after return */ PUT /* Put AC after return */ . . . 1: IMMAC 0xFF /* Change AC to all ones */ PUT /* Output 0xFF */ RET /* Return */ HALT 0x1D /* Failed to return */ The register AC will initially be set to zero. The subroutine will change the AC value to all ones (hexadecimal "FF") and put that value to the Output port. This will be positive evidence that the subroutine was successfully called. After the return, The AC will be set to hexadecimal "AA" (alternating zeros and ones) and written to the output port. Return failures will be caught by the Halt instruction at the end. With reliable loops and subroutines, shift and Add instruction testing should be easy. A single zero and a single one bit should be shifted through the AC to reveal any s-a-0 and s-a-1 faults between bits in the shift logic. Both directions (right and left) should be exercised. The Add instruction may be tested exhaustively because the SP.1 datapath is only eight bits wide. Selective testing will be required for sixteen, 32 or 64-bit datapaths, for example, to decrease test time. The Noop instruction poses an interesting test problem. The designer or diagnostic program must demonstrate that the execution of a Noop instruction has not had any effect on the state elements in the machine other than the instruction pointer. This is a point for reflection. Section 4 - Test evaluation. What assurance do we have that the diagnostic program will completely validate the ISA model or test an implementation of the SP.1 ISA? This is the issue of coverage raised to the architectural level. Luckily, we can turn to software engineering techniques for some help. * Every path through the ISA program should be executed at least once. * All special cases and conditions must be exercised. * Input data must be devised for all exceptional values and to detect (or even isolate) s-a-0 and s-a-1 faults. If all three items are faithfully executed, coverage will be high. The architectural design team should make maximum use of the controllability and observability available in software. We constrained ourselves in the discussion above to make the diagnostic program suitable for prototype debugging and quality assurance. The observability and controllability under those circumstances are low due to the limited number of SP.1 input and output ports. During ISA evaluation, however, the model is more readily controlled and the trace output can be quite extensive (including the values of "invisible" storage elements like the Z flag and CR register.) Section 5 - Test application. The inputs to the ISA validation process are the ISA model (simulation program), the diagnostic program to be loaded into the simulated program memory and the test patterns to be used while the diagnostic runs on the simulator. A trace will be produced showing the sequence of instructions executed, register contents, input values and output port values. The design team should consider reading the Input port values from a disk file permitting repeatability. Trace output should initially be hand-checked and saved on disk. Once the diagnostic executes successfully, the trace can be compared with future runs using a Unix comparison utility like "diff." Section 6 - ISA implementation The design of a computer is decision making process. The ISA specifies the behavior which the system should exhibit and it is the job of the design engineer to translate that abstract specification for the machine to a working product. Many engineering constraints must be satisfied within the project schedule and budget, namely, acceptable performance, technological feasibility, the target unit cost, manufacturability and maintainability. ------------ Conditions ---------- | |<-------------| | | Controller | | Datapath | | |------------->| | ------------ Control ---------- Figure 1 - Separation of data and control. The next several chapters will explore this process. In Chapter 6, we discuss design in the large and the use of modularity in design. Next, we describe the building blocks that will be used to implement the SP.1 in Chapter 7. We will follow the traditional separation of data and control during the design of the SP.1. Data is stored and manipulated in the "datapath" under centralized control (Figure 1.) The controller sequences the flow and modification of data items by sending control signals to the datapath. The datapath generates condition signals (e.g., the Z flag) to which the controller responds and modifies the sequence of control operations. A synchronous timing discipline is used. Although datapath design is addressed before control programming, a good computer designer considers event sequencing and datapath parallelism in tandem. (We have to start somewhere, however!) Chapter 8 presents a collection of heuristic rules for the translation of an SP.1 ISA to an initial datapath design. A flow graph technique is introduced in Chapter 9 for the expression of control events, In Chapter 10, we take up the question of datapath style and examine trade-offs in sequencing and parallelism. The estimation of execution speed, space and power consumption is the subject of Chapter 11. The internal organization of the PDP-11/40 is discussed in Chapter 13, leading to the topics of multi-phase clocks and instruction pipelining. Copyright (c) 1987-2013 Paul J. Drongowski