Chap 3: part 1. Instruction set design ---------------------- GOALS: ----- - An example instruction set - The stored-program concept - Design principles of instruction sets: to cope up with the implications of the stored program concept ------------------------------------------------------------------ Concepts: ======== - An example instruction set: Scenario: How is a computer different from a calculator or a PDA ? I want to build this computer ? What exactly do I want to build ? Big picture: - Instruction set is what the computer implements. Driven by: Reqt 1. functionality (from formal logic) and expressiveness i.e. ease/efficiency of mapping higher level language to it, Reqt 2. hardware technology (ease of implementation) Reqt 3. performance considerations (speedup in coding and running real programs) - Any of these three factors change significantly => possible demand for new/enhanced instruction set architecture Bottom up: - Lets explore how an instruction set can be built. Qn: What are the characteristics of an instruction set in terms of its capabilities or functionality as seen by the higher layers ? - Turing machine: bits in memory; read, process, write, move left or right. - Ans: The architecture (instruction set) should allow one to do whatever a Turing machine can do ! Qn: What is the minimum number of instructions you need in the set to do this ? Ans: An instruction set which contains only one instruction can do this ! sbn a, b, c # Subtract and Branch if negative # Mem a = Mem a - Mem b; Assuming random access memory # ; - can read/write to memory # ; - can perform arithmetic operations # if Mem a < 0, go to c; Assuming stored program concept # ; - can move head i.e. go to another # ; point of control in the state machine - Three issues: - Implementation is easy (reqt 2): we would like to keep this property - Programming in this is cumbersome (reqt 1 not met!) => need an expanded interface, which allows more expressiveness, and directness of expression - Performance (execution time of real programs) will be slow since instruction count huge (reqt 3 not met!) Remember always to consider these three requirements in instruction set design ! ---------------------------------------------------------------------------- - Stored-program concept: Scenario: Where to keep the commands of the program ? Can I build new hardware for it ? Or build special ROMs to store it ? How to refer to other commands (positions) in the program ? Problem: - new hardware per program costly. - ROMs per program inflexible. Even a ROM assumes that instructions can be represented as a sequence of zeros and ones. To refer to other positions in program (for random access branch), we need to have addresses for each instruction. - Possibility: you can have separate RAMs for programs and data => 2 different address spaces. Instead, why not store both data and programs in RAM ? Big Picture: - Instructions are represented as numbers {REPRESENTATION/CODING} - Programs can be stored in memory to be read/written just like data {ADDRESSING} Bottom up: (Implications of stored program concept) 1. Instruction format: Need NUMERICAL REPRESENTATION for instructions which is called an instruction format. - Instruction format contains opcodes and operands. What are they ? - Opcodes and operands: The instruction format should have specific codes for control operations (called opcodes or instruction codes) and data objects (called operands) 2. Address space: Instructions of a program have addresses just like data, and more importantly, for ease of implementation (reqt 2) they share the same address space as data in memory. However this does not mean that instructions and data should not be intertwined ! In fact, some older architectures allowed "self-modifying" instructions where some instructions were like data for other instructions !! Needless to say, such cannibalistic programs went out of fashion quickly, and typically data is well separated from instructions (except for immediate data). In some architectures, the address spaces in memory are logically partitioned so that instructions cannot overlap with data ... (eg: Intel 80x86 architecture). 3 Addressing modes: Instructions refer (or address) data => INSTRUCTION FORMAT MUST HAVE SPACE TO CONTAIN DATA ADDRESSES Eg. If an address in a 2^32 word memory needs 32 bits for representation, i.e., every data object (operand) should ultimately have a 32-bit address. Now, this operand address should be implicitly or explicitly specified in the instruction format. The problem occurs because instructions themselves are sometimes only 32 bits long (and this space must be used to both opcodes and operands together) !! => ADDRESSING MODES ALLOW OPERANDS TO BE ENCODED WITH FEWER NUMBER OF BITS. {addressing modes are also used to easily map higher level constructs like arrays to machine language instructions} 4. Registers: was primarily devised as a coding tool. - Registers split the addressing space into two: a large memory address space (30- or 62-bits) and a small register address space (3-5 bits). This allows compact instruction formats because they can now code register addresses in their operand field, which possibly in combination with register values can indirectly address the larger address space memory. Introduction of registers - allows shorter instructions - but complicates addressing modes and their implementation - and requires load/store to transfer data between the multiple address spaces. - allows data as well as instructions to reside in them, though processors make distinctions Side effect: The register also was implemented on-board the processor which meant that there was fast storage available for variables, which enabled arithmetic operations to be performed using operands stored in registers only. This affected the performance requirement (reqt 3}. ------------------------------------------------------------------------ - Architectural principles (for instruction set design) Scenario: Now we've created a wave of implications and several possibilities for instruction sets with the stored program concept. How to make the architectural choices such as fixed instruction length or variable, what types of addressing modes to allow, how many registers ? Ans: go back to the driving requirements! - implementation simplicity (hardware tech) - Expressiveness and ease of translations/optimization from higher layer language to machine language (compiler tech) - Performance (running benchmarks) BIG PICTURE: Come up with a set of principles... - Simplicity favors regularity: Regularity => efficient coding, simpler model for implementation - Smaller is faster: esp at the lowest layer (hardware), requires less real estate on chips and code space in instruction format. - Good design demands a compromise: tradeoff the uncomon case. The ugly side ... - Make the common case fast Bottom up: (MIPS architecture) - Arithmetic performed only on registers - Negative or floating point numbers can be used. - Access memory with only 2 instructions (lw, sw) - Allow multiple data types: characters (one byte), short integers (two bytes), and words (four bytes). But require data to be aligned to a word boundary, even though memory is byte addressable. Therefore, memory = 2^30 words. - Allow multiple instruction formats (R- (reg), I- (immediate), J- (jump)), but keep instruction sizes fixed (32 bits) - Limited number of conditional branch instructions (beq, bne, slt) for loops, if, switch statements. Others are implemented using slt. - unconditional jumps and jal for procedures - immediate mode => operand only 16 bits. More than that => use lui and $at register by assembler {More details in part 2} CONCEPT Checklist (Part 1) ----------------- - Stored program. Program instructions have a numerical representation just like data and are stored in the same address space as data. - Implications of stored program concept: instruction format possibilities, addressing mode possibilities, registers. - Choices from these possibilities, and functionality per instruction is driven by architectural principles - Arithmetic, data transfer, branch/jump, procedure instructions in MIPS