Computer Architecture What is it, and how is it related to ...

Computer Architecture What is it, and how is it related to ...

COMP 411: Computer Organization Instruction Sets, Episode 1 Don Porter 1 COMP 411: Computer Organization Representing Instructions Todays topics von Neumann model of a computer Instruction set architecture MIPS instruction formats Some MIPS instructions Reading P&H textbook Ch. 2.1-2.2, Ch. 2.5-2.6 2 COMP 411: Computer Organization A General-Purpose Computer The von Neumann Model Many architectural models for a general-purpose computer have been explored Most of todays computers based on the model proposed by John von Neumann in the late 1940s Its major components are: Input/

Output Central Processing Unit Main Memory Central Processing Unit (CPU): Fetches, interprets, and executes a specified set of operations called Instructions. Memory: storage of N words of W bits each, where W is a fixed architectural parameter, and N can be expanded to meet needs. I/O: Devices for communicating with the outside world. 3 COMP 411: Computer Organization Instructions and Programs What are instructions? the words of a computers language Instruction Set the full vocabulary Stored Program Concept The idea that instructions and data of many types can be stored in memory as numbers, leading to the stored program computer Distinct from application-specific hardware, which is hardwired to perform fixed-function processing on inputs Distinct from punched tape computers (e.g., looms) where instructions were not stored, but streamed in one at a time 4 COMP 411: Computer Organization

Anatomy of an Instruction An instruction is a primitive operation Instructions specify an operation and its operands (the necessary variables to perform the operation) Types of operands: immediate, source, and destination Operation $X is a convention to denote the contents of a register, which is a location inside the CPU. In contrast, immediate operands indicate the value itself add $t0, $t1, $t2 Operands (variables, arguments, etc.) Source Operands Destination Operand addi $t0, $t1, 1 Immediate Operand 5

COMP 411: Computer Organization Meaning of an Instruction Operations are abbreviated into opcodes (1-4 letters) Instructions are specified with a very regular syntax First an opcode followed by arguments Usually (but not always) the destination is next, then source Why this order? Arbitrary but analogous to high-level language like Java or C add $t0, $t1, $t2 implies The instruction syntax provides operands in the same order as you would expect in a statement from a high level language. (int) t0 = t1 + t2 6 COMP 411: Computer Organization Being the Machine! Instruction sequence Instructions are executed sequentially from a list unless some special instructions alter this flow Instructions execute one after another therefore, results of all previous instructions have been computed Instructions

Variables add $t0, $t1, $t1 add $t0, $t0, $t0 add $t0, $t0, $t0 sub $t1, $t0, $t1 What is this program doing? $t0: 0 1224 48 $t1: 6 42 $t2: 8 $t3: 10 7 COMP 411: Computer Organization What did this machine do? Lets repeat the simulation, this time using unknowns CLASS: What is this machine doing? Knowing what the program does allows us to write

down its specification, and give it a meaningful name Instructions times7: Variables add $t0, $t1, $t1 $t0: w 2x4x 8x add $t0, $t0, $t0 $t1: x add $t0, $t0, $t0 $t2: y sub $t1, $t0, $t1 $t3: z 7x 8 COMP 411: Computer Organization

Looping the Flow Need something to change the instruction flow go back to the beginning a jump instruction with opcode j the operand refers to a label of some other instruction for now, this is a text label you assign to an instruction in reality, the text label becomes a numerical address Instructions times7: Variables add $t0, $t1, $t1 $t0: w 8x 56x 392x $t1: x 7x49x 343x add $t0, $t0, $t0 $t2: y sub $t1, $t0, $t1 $t3: z add $t0, $t0, $t0

j times7 An infinite loop COMP 411: Computer Organization Open Questions in our Simple Model We will answer the following questions next WHERE are INSTRUCTIONS stored? HOW are instructions represented? WHERE are VARIABLES stored? How are labels associated with particular instructions? How do you access more complicated variable types: Arrays? Structures? Objects? Where does a program start executing? How does it stop? 10 COMP 411: Computer Organization The Stored-Program Computer The von Neumann model: Instructions and Data stored in a common memory (main memory) Sequential semantics: All instructions execute sequentially (or at least appear sequential to the programmer)

Main Key idea: Memory holds not only data, but coded instructions that make up a Central Processing program. CPU fetches and executes instructions from memoryUnit ... The CPU is a hardware interpreter Program IS simply data for this interpreter Memory instructi instructi on on instructi on data data data Main memory: Single expandable resource pool - constrains both data and program size - dont need to make separate decisions of how large of a program or data memory to buy 11 COMP 411: Computer Organization registers

Anatomy of a von Neumann Computer control Data Path address Control Unit status data address instructions MEMORY Register 0 Register 1 +1 PC 1101000111011 R1 R2+R3 INSTRUCTIONS coded in binary Register 31 Register File

PROGRAM COUNTER or PC: Address of next instruction to be executed Control Unit has circuitry inside to translate instructions into control signals for data path 12 COMP 411: Computer Organization Instruction Set Architecture (ISA) Definition: The part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O An ISA includes a specification of the set of opcodes (machine language), and the native commands implemented by a particular processor 13 COMP 411: Computer Organization Instruction Set Architecture (ISA) Encoding of instructions raises interesting choices... Tradeoffs: performance, compactness, programmability Complexity How many different instructions? What level operations? Level of support for particular software operations: array indexing, procedure calls, polynomial evaluate, etc. Reduced Instruction Set Computer (RISC) philosophy: simple instructions, optimized for speed

Uniformity Should different instructions be same size? Take the same amount of time to execute? Trend favors uniformity simplicity, speed, cost/power Mix of Engineering & Art... Trial (by simulation) is our best technique for making choices! Our representative example: the MIPS architecture COMP 411: Computer Organization The big picture A few things to note: Memory is distinct from data path Registers are in data path Program is stored in memory Control unit fetches instructions from memory Control unit tells data path what to do Data can be moved from memory to registers, or from registers to memory All data processing (e.g., arithmetic) takes place within the data path registers control

Data Path address Control Unit status data address MEMORY instructions 15 COMP 411: Computer Organization MIPS Programming Model a representative simple RISC machine Processor State (inside the CPU) PC Main Memory 00 Addresses r0 r1 r2

000000....0 ... 32 bit words r31 General Registers: A small scratchpad of frequently used or temporary variables 0 4 8 16 20 31 3 0 2 1 0 32 bit words (4 bytes) next instruction

In Comp 411 well use a clean and sufficient subset of the MIPS-32 core Instruction Fetch/Execute loop: Fetch/Execute loop: set. fetch fetchMem[PC] Mem[PC] PC PC= =PC PC+ + 44 execute executefetched fetchedinstruction instruction (may (maychange changePC!) PC!) repeat! repeat! MIPS uses byte memory addresses. However, each instruction is 32-bits wide, and *must* be aligned on a multiple of 4 (word) address. Each word

contains four 8-bit bytes. Addresses of consecutive 16 instructions (words) differ by 4. COMP 411: Computer Organization Some MIPS Memory Nits Memory locations are 32 bits wide BUT, they are addressable in differentsized chunks short2 8-bit chunks (bytes) byte3 byte2 16-bit chunks (shorts) Addr 32-bit chunks (words) 2 0: 3 64-bit chunks (longs/double) 6 4: 7 31 30 29 3210 We also frequently need 8: 12: access to individual bits! (Instructions help w/ this) Every BYTE has a unique address (MIPS is a byte-addressable machine) Every instruction is one word short0 byte1 byte0 1

0 5 4 12 10 9 8 15 14 13 12 4 long0 long8 17 COMP 411: Computer Organization MIPS Register Nits There are 32 named registers [$0, $1, . $31] The operands of all ALU instructions are registers

This means to operate on a variables in memory you must: Load the value/values from memory into a register Perform the instruction Store the result back into memory Going to and from memory can be expensive (4x to 20x slower than operating on a register) Net effect: Keep variables in registers as much as possible! Special purpose and conventions 2 registers have specific side-effects (ex: $0 always contains the value 0 more later) 4 registers dedicated to specific tasks by convention 26 available for general use, but constrained by convention 18 COMP 411: Computer Organization MIPS Instruction Formats All MIPS instructions fit into a single 32-bit word Every instruction includes various fields: a 6-bit operation or OPCODE specifies which operation to execute (fewer than 64) up to three 5-bit OPERAND fields each specifies a register (one of 32) as source/destination embedded constants also called literals or immediates 16-bits, 5-bits or 26-bits long sometimes treated as signed values, sometimes unsigned

There are three basic instruction formats: R-type, 3 register operands (2 sources, destination) I-type, 2 register operands, 16-bit constant J-type, no register operands, 26-bit constant OP r s OP OP r s rt rt rd shamt func 16-bit constant 26-bit constant

COMP 411: Computer Organization MIPS ALU Operations Sample coded operation: ADD instruction R-type:0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 op = 0x00 func = 0x20 rd = 10 rs = 11 dictating an dictating an Reg[10] ALU function Reg[11] add source rt = 9destination unused Reg[9] fields are source set to 0 What we prefer to write: add $10, $11, $9 (assembly language) The convention with MIPS assembly language is to specify the destination operand first, followed by source operands. add rd, rs, rt: Reg[rd] = Reg[rs] + Reg[rt] Add the contents of rs to the contents of rt; store the result in rd References

to register contents are prefixed by a $ to distinguish them from constants or memory addresses Similar instructions for other ALU operations: arithmetic: add, sub, addu, subu compare: slt, sltu logical: and, or, xor, nor shift: sll, srl, sra, sllv, srav, srlv 20 COMP 411: Computer Organization Shift operations Shifting is a common operation applied to groups of bits used for alignment used for short cut arithmetic operations X << 1 is often the same as 2*X X >> 1 can be the same as X/2 For example: X = 2010 = 000101002 Left Shift: (X << 1) = 001010002 = 4010 Right Shift: (X >> 1) = 000010102 = 1010

Signed or Arithmetic Right Shift: (-X >>> 1) = (111011002 >>> 1) = 111101102 = -1010 COMP 411: Computer Organization MIPS Shift Operations Sample coded operation: SHIFT LOGICAL LEFT instruction R-type:0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 op = 0x00 func = 0x00 rd = 2 unused dictating an dictating an Reg[2] ALU function set to sll rt = 2destination shamt = 4 0 Reg[2] dictates a source shift of 4bits Assembly: sll $2, $2, 4 sll rd, rt, shamt: Reg[rd] = Reg[rt] << shamt Shift the contents of rt to the left by shamt; store the result in rd 22 COMP 411: Computer Organization MIPS Shift Operations

Sample coded operation: SLLV (SLL Variable) R-type:0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 op = 0x00 func = 0x04 rd = 2 shift dictating an dictating an Reg[2] ALU function amount sllv in rs rt = 2destination unused set Reg[2] to 0 source This is peculiar syntax for MIPS, in this ALU instruction the rt operand precedes the rs operand. Usually, its the other way around Assembly: sllv $2, $2, $8

Different flavor: Shift amount is not in instruction, but in a register sllv rd, rt, rs: Reg[rd] = Reg[rt] << Reg[rs] Shift the contents of rt left by the contents of rs; store the result in rd 23 COMP 411: Computer Organization MIPS ALU Operations with Immediate addi instruction: adds register contents, signed-constant: I-type:0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 OP = 0x08, dictating addi rs = 11, Reg[11] source rt = 9, Reg[9] destination constant field, indicating -3 as second operand (sign-extended!) Symbolic version: addi $9, $11, -3 addi rt, rs, imm: Reg[rt] = Reg[rs] + sxt(imm) Add the contents of rs to const;

store result in rt Similar instructions for other ALU operations: arithmetic: addi, addiu compare: slti, sltiu logical: andi, ori, xori, lui Immediate values are sign-extended for arithmetic and compare operations, but not for logical operations. 24 COMP 411: Computer Organization Why Built-in Constants? (Immediate) Where are constants/immediates useful? SMALL constants used frequently (50% of operands) In a C compiler (gcc) 52% of ALU operations use a constant In a circuit simulator (spice) 69% involve constants e.g., B = B + 1; C = W & 0x00ff; A = B + 0; Examples: addi slti andi ori $29, $8, $29,

$29, $29, 4 $18, 10 $29, 6 $29, 4 25 COMP 411: Computer Organization First MIPS Program (fragment) Suppose you want to compute the expression: f = (g + h) (i + j) where variables f, g, h, i, and j are assigned to registers $16, $17, $18, $19, and $20 respectively what is the MIPS assembly code? add $8,$17,$18 add $9,$19,$20 sub $16,$8,$9 # (g + h) # (i + j) # f = (g + h) (i + j) Questions to answer: How did these variables come to reside in registers? Answer: We need more instructions which allow data to be explicitly loaded from memory to registers, and stored from registers to memory 26 COMP 411: Computer Organization MIPS Register Usage Conventions Some MIPS registers assigned to specific uses by convention, so programmers can combine code pieces

will cover the convention later $0 is hard-wired to the value 0 Name $zero $at $v0-$v1 $a0-$a3 $t0-$t7 $s0-$s7 $t8-$t9 $gp $sp $fp $ra Register number 0 1 2-3 4-7 8-15 16-23 24-25 28 29 30 31 Usage the constant value 0 assembler temporary (for assembler use) values returned by procedures/functions arguments provided to procedures/functions temporaries (for scratch work)

saved registers (saved across procedure calls) more temporaries global pointer (tracks start of process's space) stack pointer (tracks top of stack) frame pointer (tracks start of procedure's space) return address (where to return from procedure) COMP 411: Computer Organization Continue next lecture More instructions accessing memory branches and jumps larger constants multiply, divide etc. 28

Recently Viewed Presentations

  • Improving outcomes in Atrial Fibrillation GLOS CCG AGM

    Improving outcomes in Atrial Fibrillation GLOS CCG AGM

    Time taken to do an ecg cf dress wound. QOF AF Statistics (March 14) Stoke Road Practice . AF prevalence - 2.6% (see footnote) National ... method of measurement such as the Rosendaal method for computer‑assisted dosing or proportion of...
  • Non-convex Robust PCA

    Non-convex Robust PCA

    Subspace Pursuit [Dai & Milenkovic'2008] OMPR [J., Tewari, Dhillon'2010] Partial hard thresholding and two-stage family [J., Tewari, Dhillon'2010] Empirical Results (d) Hard Thresholding. ... Lemma 2: Davis-Kahn style result for matrix perturbation.
  • Aiming for Deep and Enduring Understanding Six Facets

    Aiming for Deep and Enduring Understanding Six Facets

    Aiming for Deep and Enduring Understanding Six Facets of Understanding Explanation Interpretation Application Perspective Empathy Self-Knowledge Enduring Understanding: Understand how the relative movements of the Earth, moon, and sun account for the observed moon phases.
  • BASE STATION SETUP Considerations and choices 1. Operating

    BASE STATION SETUP Considerations and choices 1. Operating

    HF: New Carolina style Windom: between trees, 20-30 ft high, 4:1 balun, 21 feet vertical coax radiating section, 50 ohm coax feed-line to tuner. 40 meter ½ WL Windom = 67 feet; 80 meter ½ WL Windom = 133 feet.
  • Credit Risk Management: the Next Great Financial Challenge

    Credit Risk Management: the Next Great Financial Challenge

    Managing Credit Risk: The Challenge in the New Millenium Edward I. Altman (Seminar Outline) Subject Area Credit Risk: A Global Challenge in High and Low Risk Regions The New BIS Guidelines on Capital Allocation Credit Risk Management Issues - Credit...
  • Web Services Integration Security

    Web Services Integration Security

    External Interfaces Update May 21, 2007 Daryl Shing Agenda Outcomes from recent API sub-group meetings Further Web Services Status of the Interface Specification Outcomes from recent API sub-group meetings Agreed that the specification for the initial release of services could...
  • The good, the bad, and the ugly - Koç Üniversitesi

    The good, the bad, and the ugly - Koç Üniversitesi

    The good, the bad, and the ugly. The early 1970s. ... Graham Nash (The Hollies) Neil Young (Buffalo Springfield and Crazy Horse): only semi-committed. Ahmet Ertegun (Atlantic Records) "Woodstock" (written by Joni Mitchell) ... Roberta Flack. 1973
  • TRB&#x27;s National Cooperative Highway Research Program (NCHRP ...

    TRB's National Cooperative Highway Research Program (NCHRP ...

    Audience is TIM program mid-level managers & analysts. Research Approach. Review past and ongoing efforts on TIM performance measures, outcomes, and monetization . Engage State Stakeholder and broader public on guidance needs. Compare methods for estimating and monetizing TIM outcomes...