Computer System and Application,Chapter 6: Instruction System of CPU,Concepts of Instruction System,Instruction system: machine instruction set Interface between hardware and software Determine CPUs structure and function Determine structure and function of programming language The same part viewed by architect and programmer A large part of CPU design task is implementing instruction set Different CPU architecture, different instruction set RISC vs CISC Contents of designing instruction set Instruction format design Instruction function design Data type support Addressing mode design,Components of An Instruction,Instruction set The collection of different instructions that the processor can execute Tenshundreds of instructions An instruction includes Opcodes Addressing mode flag Addresses: source operands and result operands Main memory or virtual memory Register I/O devices Source operand may be immediate operand Address of next instruction: explicit or implicit Machine instruction is presented as a sequence of 0,1 codes Many formats exist in instruction set,4,Opcode Optimization Design,Frequently used opcode representations Fixed-length opcode Huffman encoding Extended Huffman encoding Fixed-length opcode One byte length Simple hardware, but total opcode is too long Used in RISC CPU Huffman encoding Variable opcode length Shortest average opcode length Extended Huffman encoding Combining fixed-length and Huffman encoding,5,Huffman Encoding,Principle Frequently events are represented by short code Average code length is shortest Theory basis is entropy coding Entropy Shortest average encoding length pi: usage probability of an opcode in program : amount of information of the opcode Redundant amount of information H: average code length of an encoding mode,6,Example for Huffman Encoding,Suppose a CPU has 7 opcodes and occurring probability in program is shown as the table. Problems: If fixed-length opcode is used,how many bits are the opcode? How many bits are the shortest average opcode(entropy)? How much is redundant amount of information for fixed-length opcode?,7,Solutions,7 opcodes, so in fixed-length mode, 3bits are needed Entropy Redundant amount of information for fixed-length opcode 35% is redundant information,8,Opcode Encoding Method Based on Huffman,Encoding using Huffman tree,also called minimum probability merging Step1: construct Huffman tree Step2:encoding branches Huffman tree constructing procedure in above example Arrange the probabilities of 7 opcodes high-down Merging probable nodes in binary tree from right to left Encode each branch using 0 or 1 Left branch is 0 and right branch is 1 0,1 sequence from the root to a leaf node is the encoding of the opcode See next slide,9,Huffman Tree,10,Average Code Length of Huffman Encoding,Average code length pi: usage probability of ith opcode in program li: length of ith opcode According to values of the fig. Average code length: Amount of redundant information: Huffman encoding approaches optimized entropy,11,Pros and Cons of Huffman Encoding,Pros Short average code length Little redundant information Cons Opcode irregularity No easy for instruction decoding and compiling Notes Huffman encoding is not unique Total code length and average code length are unique,12,Extended Huffman Encoding,Huffman encoding on the whole combines with local fixed-length encoding Trade-off between Huffman and fixed-length Simplify decoder and compiler Multiple encoding methods,13,Address Code Design,Total address length depends on the number of addresses, types and addressing modes Typical addresses in instructions 3,2,1,0 Too many addresses may exist, but seldom used Addresses selection rules Make the program shortest Make the program fastest Shortening address length to avoid too long instruction Indirect addressing Register indirect addressing Index addressing,14,Instruction Format Design,It is a very complicated problem, limited by Instruction function and length Fields and bits of each field Addressing modes Length of main memory unit Many instruction formats exist in a instruction set Trade-off between opcode length and addressing ability is needed Variable opcode Multiple opcodes,15,X86 Instruction Format,The x86 is equipped with a variety of instruction formats The instruction format is very flexible Typical CISC instructions,16,Data Types,Data type design is an important content for instruction set Influencing the structure and function of CPU Determining the data types of HLL Typical data types Addresses Numbers Characters Logical data Special data types Lists Strings,17,Numbers,Numbers in computer are limited and discrete Typical numbers Binary integer or binary fixed point Binary floating point Decimal Binary integer , its value in Twos Complement Representation is Where, , overflow will occur if a value exceeds this scope,18,Numbers,Binary floating point numbers Any float-point number can normalized as or 0.1,1. a