Cheat Sheet 3g5k2q

LECTURE 1 - COMPUTERS Definition of a Computer •Varied versions of definition of a “computer” –A computer is a fast electronic calculating machine that accepts digitized input information, processes it according to a list of internally stored instructions, and produces the resulting output information •From Computer Organization by Hamacher, Vranesicand Zaky –A computeris a programmable machine that receives input, stores and manipulates data, and provides output in a useful format. •From wikipedia –A computeris an electronic device that manipulates information or "data." It has the ability to store, retrieve, and processdata. •From GCF online class Computer Basics Computer Hardware vs. Computer Organization •Computer hardware –Electronic circuits and equipment that constitutes the computer •Computer Organization –Operational units and their interconnections that realize/implement the architectural specifications Classes of Computers •Desktop computers –General purpose, variety of software –Subject to cost/performance tradeof •Server computers –Network based –High capacity, performance, reliability –Range from small servers to building sized •Embedded computers –Hidden as components of systems –Stringent power/performance/cost constraints Below Your Programs •Application software –Written in high-level language •System software –Compiler: translates HLL code to machine code –Operating System: service code •Handling input/output •Managing memory and storage •Scheduling tasks & sharing resources

•Hardware –Processor, memory, I/O controllers Five Classic Components of a Computer •Input device –A mechanism through which the computer is fed information –Keyboard, mouse, … •Output device –A mechanism that coveys the result of a computation –Screen, printer, … •Memory –The storage area in which programs and data are kept –DRAM (dynamic random access memory), SRAM (static random access memory), cache, hard drives, flash memory, … •Details to be discussed in CS365 –Main memory and secondary memory –Volatile memory vs. nonvolatile memory •Datapath •Control A Safe Place for Data •Volatile main memory –Loses instructions and data when power of •Non-volatile secondary memory –Magnetic disk –Flash memory –Optical disk (CDROM, DVD) The Processor •Also called U (Central Processing Unit) •Comprises two main components –Datapath •The component of the processors that performs arithmetic operations –Control •The component of the processor that commands the datapath, memory, and I/O devices according to the instructions of the program Communicating with other Computers •Computer Networks –An important component of today’s computer –a collection of computers and devices interconnected by communications channels that facilitate communications among s and allows s to share resource –Local area networks, wide area networks, … –Details to be discussed in CS380 •Advantages of networked computers –Information exchange

between computers at high speed –Resources sharing –Non-local access Additional Terminologies •Datacenter •Size of data –Byte, MegaByte(MB), GigaByte(GB) –Terabyte (240or 1012bytes) –Petabyte(1K terabytes, i.e. 1000 or 1024 terabytes) Back to Computer Science … •Abstractions –Abstraction helps us deal with complexity •Hide lower-level detail –Instruction set architecture (ISA) •The hardware/software interface –Application binary interface •The ISA plus system software interface –Implementation •The details underlying and interface Languages of Hardware •To speak to electronic hardware –Electrical signals –Signals: high/low –Switches: on/of •Fundamentally, what language does a machine understand? –Binary digit –Instruction: a command that computer hardware understands and obeys •Can be represented in binary format •Interface of hardware and software –Instruction set architecture From High-Level Language to the Language of Hardware •High-level programming languages –Java, C++, … •Language of the hardware –Instructions and data represented in binary format •Translation process –Compiler: a program that translates a program written in high-level language into low-level language (i.e. assembly language) statements –Assembler: a program that translates symbolic version of instructions (in assembly language) into binary version From High-Level Language to Machine Language •High-level language –Level of abstraction closer

to problem domain –Provides for productivity and portability •Assembly language –Textual representation of instructions •Hardware representation –Binary digits (bits) –Encoded instructions and data Assembly Language vs. Machine Language •Assembly language –A symbolic representation of machine instructions •Machine language –A binary representation of machine instructions •Instruction –A command that computer hardware understands and obeys Information Representation •Binary computers •Bits •Bytes –Megabyte(MB), Gigabyte (GB), terabyte (TB), Petabyte, … •Words, double words, … •Integer and floating point numbers •Character sets –ASCII, Unicode, … •Lecture 2 will discuss data representation in more details Lecture 3a: MIPS Architecture Instruction Set Architecture Instruction Set Architecture (ISA) Also called architecture An abstract interface between hardware and lowest-level software Including the design of instructions and machine organization Machine organization: including s, memory organization, … A Typical U Structure The U consists of a data section (also known as the datapath) containing s and an ALU, and a control section. Machine Instructions In general a machine Instruction has the following fields (parts): An opcode field, which specifies the operation to be performed. One or more of address fields, each one is either a memory address or a address ('s number). A mode field, which specifies the way the address field is to be interpreted.

This field may be implicit The address fields of an instruction may consist one or two or three memory or addresses. If all address fields of an instruction are addresses, we call the machine 1-,2-,or 3- address machine. If all address fields of an instruction are memory addresses, we call the machine 1-,2-,or 3-memory address machine. For two and three-address machine, the address fields may include both and memory addresses. We call the machine 2-(or 3-)-memory address machine. Java Virtual Machine Architecture is an example of 0-memory address machine Historical Perspective Accumulator architecture Stack machines Sufered bottle-neck problem Later Architectures Special-purpose or dedicated s General purpose (GPR) architectures Varied number of GPRs in popular machines Load-store architecture Load Store Architecture Only load or store instruction can access memory Load: read memory Store: write memory All other instructions work on operands stored in s Also called - architecture Otherwise, it’s called -memory architecture For example, in reg-mem architecture, an add instruction may have one or two operands stored in the memory Architectural Development of Computers (1) Architectural Development of Computers (2) RISC and CISC Complex Instruction Set Computer (CISC) Reduced Instruction Set Computer (RISC) virtually all new instruction sets since 1982 have been RISC An example of CISC machines

VAX: minimize code size, make assembly language easy instructions from 1 to 54 bytes long! RISC and CISC: Features ◆A RISC architecture has the following properties: - Memory accesses are restricted to load and store instructions, and datamanipulation instructions are -to-; - Addressing modes are limited in number; - Instruction formats are all of the same length; Instructions perform elementary operations. ◆ A purely CISC architecture has the following properties: - Memory access is directly available to most types of instructions; - Addressing modes are substantial in number; - Instruction formats are of diferent lengths; - Instructions perform both elementary and complex operations. RISC vs. CISC Addressing Modes The various addressing modes that are defined in a given ISA define how instructions in that architecture identify the operand(s) of each instruction. An addressing mode specifies how to calculate the efective memory address of an operand by using information held in s and/or constants contained within an instruction or elsewhere. Simple Addressing Modes for Data Operand(s) contained in (s) Immediate Operand available in instruction Base plus ofset Efective address = ofset + contents of specified base (operand in memory location of efective addr.) Indexed absolute Efective address = address + contents of specified index I NTEGER INSTRUCTION SET Add add Rd, Rs, Rt 111 Add Immediate addi Rt, Rs, Imm III Add Immediate Unsigned addiu Rt, Rs, Imm III

Add Unsigned addu Rd, Rs, Rt 111 And and Rd, Rs, Rt 111 And Immediate andi Rt, Rs, Imm 111 Branch if Equal beq Rs, Rt, Label 111 Branch if Greater Than or Equal to Zero bgez Rs, Label 111 Branch if Greater Than or Equal to Zero and Link bgezal Rs, Label 111 Branch if Greater Than Zero bgtz Rs, Label III Branch if Less Than or Equal to Zero blez Rs, Label 111 Branch if Less Than Zero and Link bltzal Rs, Label 111 Branch if Less Than Zero bltz Rs, Label 111 Branch if Not Equal bne Rs, Rt, Label 111 Divide div Rs, Rt 1 138 Divide Unsigned divu Rs, Rt 1 138 Jump i Label 111 Jump and Link j al Label 111 Jump and Link j alr Rd, Rs 111 Jump jr Rs 111 Load Byte Ib Rt, ofset(Rs) 111 Load Byte Unsigned Ibu Rt, ofset(Rs) 111 Load Halfword lh Rt, ofset(Rs) 111 Load Halfword Unsigned Ihu Rt, ofset(Rs) 111 Load Upper Immediate lui Rt, Imm 111 Load Word Iw Rt, ofset(Rs) III Load Word Left Iwl Rt, ofset(Rs) 111 Load Word Right Iwr Rt, ofset(Rs) 111 Move From Coprocessor 0 mfcO Rd, Cs 111 Move From High mfhi Rd 111 Move From Low mflo Rd 111 110 M a cro I n stru ct i o n s 1 1 1 Move To Coprocessor 0 mtcO Rt, Cd 111 Move to High mthi Rs 111 Move to Low mtlo Rs 111 Multiply mult Rs, Rt 1132 Multiply Unsigned multu Rs, Rt 1 132 NOR nor Rd, Rs, Rt 111 OR or Rd, Rs, Rt 111 OR Immediate ori Rt, Rs, Imm 111 Return From Exception rfe 111 Store Byte sb Rt, ofset(Rs) 111 Store Halfword sh Rt,

ofset(Rs) 111 Shift Left Logical sll Rd, Rt, sa 111 Shift Left Logical Variable sllv Rd, Rt, Rs 1 1 1 S e t on Less Than sit Rd, Rt, Rs 111 Set on Less Than Immediate slti Rt, Rs, Imm 111 Set on Less Than Immediate Unsigned sltiu Rt, Rs, Imm 111 Set on Less Than Unsigned situ Rd, Rt, Rs 111 Shift Right Arithmetic sra Rd, Rt, sa 111 Shift Right Arithmetic Variable srav Rd, Rt, Rs 111 Shift Right Logical sri Rd, Rt, sa 111 Shift Right Logical Variable srlv Rd, Rt, Rs 111 Subtract sub Rd, Rs, Rt 111 Subtract Unsigned subu Rd, Rs, Rt 111 Store Word sw Rt, ofset(Rs) 111 Store Word Left swl Rt, ofset(Rs) 111 Store Word Right swr Rt, ofset(Rs) 111 System Call syscall 111 Exclusive OR xor Rd, Rs, Rt 111 Exclusive OR Immediate xori Rt, Rs, Imm 111 MIPS MACRO INSTRUCTIONS Absolute Value abs Rd, Rs 3/3 Branch if Equal to Zero beqz Rs, Label 1/1 Branch if Greater Than or Equal bge Rs, Rt, Label 2 Branch if Greater Than bgt Rs, Rt, Label 212 Branch if Greater Than Unsigned bgtu Rs, Rt, Label Branch if Less Than or Equal ble Rs, Rt, Label 2/2 Branch if Less Than or Equal Unsigned bleu Rs, Rt, Label 2/2 Branch if Less Than bit Rs, Rt, Label 2/2 Branch if Less Than Unsigned bltu Rs, Rt, Label 2/2 B ranch if Not Equal to Zero bnez Rs, Label 111 Branch Unconditional b Label 111 D ivide div Rd, Rs, Rt 4/41 D ivide Unsigned divu Rd, Rs, Rt 4/41 Load Address la Rd, Label 2/2 Load Immediate Ii Rd, value 2/2 Move move Rd, Rs 111 Multiply mul Rd, Rs, Rt 2/33 Multiply (with overflow exception) mulo Rd, Rs, Rt

Multiply Unsigned (with overflow exception) mulou Rd, Rs, Rt 5/35 Negate neg Rd, Rs 111 1 1 2 Appen d ix A Q u ick Referen ce Negate Unsigned negu Rd, Rs 111 Nop nop 111 Not not Rd, Rs 111 Remainder Unsigned remu Rd, Rs, Rt 4/40 Rotate Left Variable rol Rd, Rs, Rt 4/4 Rotate Right Variable ror Rd, Rs, Rt 4/4 Remainder rem Rd, Rs, Rt 4/40 Rotate Left Constant rol Rd, Rs, sa 3/3 Rotate Right Constant ror Rd, Rs, sa 3/3 Set if Equal seq Rd, Rs, Rt 4/4 Set if Greater Than or Equal sge Rd, Rs, Rt 4/4 Set if Greater Than or Equal

Unsigned sgeu Rd, Rs, Rt 4/4 Set if Greater Than sgt Rd, Rs, Rt 111 Set if Greater Than Unsigned sgtu Rd, Rs, Rt 111 Set if Less Than or Equal sle Rd, Rs, Rt 4/4 Set if Less Than or Equal Unsigned sleu Rd, Rs, Rt 4/4 Set if Not Equal sne Rd, Rs, Rt 4/4 Unaligned Load Halfword Unsigned ulh Rd, n(Rs) 4/4 Unaligned Load Halfword ulhu Rd, n(Rs) 4/4 Unaligned Load Word ulw Rd, n(Rs) 2/2 Unaligned Store Halfword ush Rd, n(Rs) 3/3 Unaligned Store Word usw Rd, n(Rs) LOOPS AND EVERYTHING ELSE Translation of a “for”

Loop Control Structure $a0 = 0; for ( $t0 =10; $t0 > 0; $t0 = $t0 -1) {$a0 = $a0 + $t0} TRANSALTES TO Li $a0, 0 # $a0 = 0 Li $t0, 10# Initialize loop counter to 10 loop: add $a0, $a0, $t0 addi $t0, $t0, -1 # Decrement loop counter bgtz $t0, loop # If ($t0 > 0) Branch to loop Translation of a “while” Control Structure while ($a1 < $a2) do { $a1 = $a1 + 1 $a2 = $a2 - 1} while: bgeu $a1, $a2, done # If( $a1 >= $a2) Branch done addi $a1, $a1, 1 # $a1 = $a1 + 1 addi $a2, $a2, -1 # $a2

= $a2 - 1 j while while done: SYS CALLS

# jump to

Servic Call Code in $v0 Arguments Results Print_ 1 $a0 = integer Print_ string 4 $a0 = &string Read_int 5 $v0= integer Read_strg 8 $a0 = &buffer Length of buffer Exit 10

$a1 =