What to Review for the Test

REVIEW FROM MIDTERM 1

What to review for the test.

●how to do binary & hex math & conversion

●how to design & verify simple circuits IE: adders, mux/demux,decoders ...

●how to speed up the internal workings of a CPU

●basic terminology

●know Boolean Algebra & how to use the laws to manipulate to simple equations

●building truth tables and how to use them including sum of products

What can you do to study?

●do homework #2, build a full-subtractor

●design a mux w/o looking it up

●multiply a few binary numbers (it teaches multiplication and addition & conversion to check the answers)

●review your notes and the overheads

●study the 1-bit ALU in the book and become familiar with how it works (Pg 166-167)

●you only need to study up to page 174

REVIEW FROM MIDTERM 2

What to review for the test.

●basic terminology

●latches (flip-flops), registers, memory units...building, addressing

●how to speed up the internal workings of a CPU

ospeed vs cost tradeoffs

●IJVM machine

ostack based machines

owriting code, registers & operation

oreading and understanding the microcode

owriting programs in assembly

oinvoking subroutines

●branch prediction (static & dynamic)

●cache

●parallel instruction execution

●Intel ISA

oinstruction formats

oaddressing modes

●DMA controller

●Interrupts & traps

Review Notes (Chapters 1 – 5)

Key Words – CHAPTER 1

Program: A sequence of instructions describing how to perform a certain task

Machine Language: A computer’s primary instructions form a language in which people can communicate with the computer

Structured Computer Organization: Computer systems can be designed in a systematic, organized way

Translation: Converting a program entirely to machine language and forgetting the earlier input

Interpretation: A program is examined and decoded, then carried out immediately

Gates: Built from transistors, and can be combined to form a 1 bit memory

Register: Can hold a single binary number up to some maximum, formed from grouped 1

Digital logic level (LEVEL 0): Contains gates, physical components

Microarchitecture level (LEVEL 1): Collection of 8 to 32 registers that form a local memory and circuit called and ALU (Arithmetic Logic Unit) which is capable of performing simple arithmetic operations

Data path: the registers are connected to the ALU, creating a path over which data flows. The basic operation of the data path consist of selecting one or two registers, have the ALU operate on them, and store the result back in some register

Microprogram: On some machines the operation of the data path is controlled by a microprogram. On machines with software control of the data path, the microprogram is an interpreter for the instructions at level 2

Instruction set architecture level (LEVEL 2): Also known as the ISA level, is 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

Operating system machine level (LEVEL 3): Instructions are identical to level 2, except some of the level 3 instructions are interpreted by the operating system and some are interpreted by the microprogram. This is also known as the “hybrid level”

Assembly language level (LEVEL 4): the program that performs the translation programs in assembly language are first translated to level 1, 2, or 3 language and then interpreted by the appropriate virtual or actual machine

Problem-oriented language level (LEVEL 5): languages designed to be used by application programmers with problems to solve. Examples C, C++, Java, PHP. Programs written in these languages are translated to level 3 or level 4 by compilers

Architecture: the set of data types, operations, and features of each level. The architecture deals with those aspects that are visible to the user of that level

Computer architecture: The study of how to design those parts of a computer system that are visible to the programmers

Hardware: Tangible objects, integrated circuits, power supplies, cables, memory, printers, etc.

Algorithms: Detailed instructions telling how to do something

Software: consists of algorithms and their computer representations (ex. Programs)

Moore’s Law: The number of transistors per square inch on integrated circuits had doubled every year since the integrated circuit was invented. Moore predicted that this trend would continue for the foreseeable future

Microcontrollers: a small computer on a single integrated circuit containing a processor core, memory, and programmable input/output peripherals

Cache memory: Used to hold the most commonly used memory words inside or close to the CPU, in order to avoid ‘slow’ accesses to main memory

MMX: Multimedia extension, these instructions were intended to speed up computations required to process audio and video. Making the addition of special multimedia coprocessors unnecessary

Key Words – CHAPTER 2

Bus: A collection of parallel wires for transmitting address, data, and control signals

Central processing unit (CPU): The ‘brain’ of the computer, it is comprised of several distinct parts

-Control Unit: Responsible for fetching instructions from main memory & determining their type

-Arithmetic logic unit (ALU): Performs operations such as addition and Boolean algebra needed to carry out the instructions

Program counter (PC): The most important register which points to the next instruction to be fetched for execution

Instruction Register (IR): Holds the instruction currently being executed

Data path cycle: The process of running two operands through the ALU and storing the result

Instruction Execution (Fetch – decode – execute)

1. Fetch the next instruction from memory into the instruction register
2. Change the program counter top point to the following instruction
3. Determine the type of instruction just fetched
4. If the instruction uses a word in memory, determine where it is
5. Fetch the word, if needed, into a CPU register
6. Execute the instruction
7. Go to step 1 to begin executing the following instruction

Interpreter: A program that fetches, examines, and executes the instructions of another program

Reduced instruction set computer (RISC): A small number of simple instructions that execute in one cycle

Complex instruction set computer (CISC): A single large instruction set that executes all at once

Pipeline: An implementation technique where multiple instructions are overlapped in execution. The computer pipeline is divided in stages. Each stage completes a part of an instruction in parallel

Latency: How long it takes to execute an instruction

Processor bandwidth: How many millions of instructions per second (MIPS) the CPU has

Single instruction stream multiple data stream (SMID): Consists of a large number of identical processors that perform the same sequence of instructions on different sets of data

Vector processor: All of the operations are performed in a single, heavily pipelined functional unit

Vector register: A set of conventional registers that can be loaded from memory in a single instruction

Multiprocessor: A system with more than one CPU sharing a common memory

Little endian: Start with big numbers and count smaller, low order

Big endian: Start with small numbers and count big, high order

Parity bit: A bit added to the end of a string of binary code that indicates whether the number of bits in the string with the value one is even or odd. Parity bits are used as the simplest form of error detecting code

Cache: Small fast memory, most heavily used memory words are kept in the cache

Locality principle: When a word is referenced, close related material nearby is also brought into the cache

Single Inline memory module: SIMM, one row of connectors on memory

Dual inline memory module: DIMM, 2 sides of connectors on memory

Small outline DIMM: SO-DIMM, used in laptops

Track: Circular sequence of bits written as the disk makes a complete rotation

Sector: Each track is divided up into some number of fixed lengths, typically containing 512 bytes of data

Preamble: Precedes sectors, allows the head to be synchronized before reading or writing

Intersected gap: A gap between consecutive sectors

Perpendicular recording: The ‘long’ dimension of the bits is not along the circumference of the disk, but vertically down into the iron oxide

Disk controller: a chip that controls the drive

BIOS: Basic Input Output System, located in the PC’s built in read only memory

IDE: Integrated drive electronics

EIDE: Extended IDE, which supports a second addressing scheme LBA (Logical block addressing)

SCSI: Small computer system interface

RAID: Redundant array of inexpensive disks. The OS treats the drives as one single large logical drive. The controller for the drives does the logical to physical translation.

Striping: Distributing data over multiple drives

Level 0:

View virtual drive as being divided among the physical drives in chunks of N sectors. Dividing the data into chunks of N sectors and distributing it is call Striping. There is no redundancy. If N = 1 then each strip is 1 sector. If a request for 6 consecutive sectors is received the controller issues 4 parallel read request to fetch the first 4 sectors, followed by 2 parallel request. Works well for requests for large blocks of data, but small or single sector request diminish or alleviate any benefits. Failure of 1 physical drive corrupts the entire logical drive

Level 1:

Exactly like level 0, except all drives are duplicated.

Data write occur to both the original & the copy write occur at level 0 speed reads can be up to twice as fast because backups can read in parallel. If a failure occurs a new drive can be substituted and the data copied to it without loss or down-time

Level 2:

Divide each byte into 2 nibbles (4 bits). Add a 3 bit Hamming code to make a 7 bit word. Read/write each 7 bit word in parallel to 7 drives. Single drive failure results in no data loss due to the use of Hamming code. Requires all drives to remain rotationally sync. Requires controller to calc 6 Hamming bits per byte (must be very fast)

Level 3:

Simplified version of level 2.using a single parity bit per nibble. Drive failure results in no data loss position of the drive in bit sequence is known controller assumes bit from that drive is 0, a parity error means it was a 1

Level 4:

Like level 0 but with an extra drive for ECC. Level 4 requires extra overhead to compute & write the ECC (because all drives must be read) so small block are inefficient. ECC drive can be a bottleneck, Drive failure results in no loss of data.

Level 5:

Eliminates the bottleneck on the ECC drive by distributing the ECC bit over all drives evenly, and drive failure results in no data loss, but recovery is complex.

DMA: Direct memory access, a controller that reads or writes data to or from memory without CPU intervention

Interrupt handler: Controller causes and interrupt forcing the CPU to immediately suspend its current program and start running a special procedure that checks for errors and informs the OS that the I/O is finished

Modulation: Varying amplitude, frequency, or phase a sequence of 1’s and 0’s can be transmitted (think sin waves)

Amplitude modulation: two different voltage levels are used for 0 and 1

Frequency modulation: The voltage level is constant but the carrier frequency is different for 1 and 0, often referred to as frequency shift keying

Phase modulation: The amplitude and frequency do not change, but the phase of the carrier is reversed 180 degrees when the data switches from 0 to 1 or 1 to 0

Full-duplex: They can transmit in both directions at the same time (on different frequencies)

Half-duplex: can only transmit in one direction at a time

Simplex: Lines that can transmit in only one direction

Character code: the mapping of characters onto integers

ASCII: American Standard code for Information Interchange

Unicode: Assign ever character and symbol a unique 16-bit value

Key Words – CHAPTER 3

Gates: Tiny electronic devices that can computer various functions of two valued signals

Circuit equivalence: another circuit that computes the same function as the original, but does so with fewer gates

Multiplexer: A circuit with 2n data inputs, one data output and N control inputs that select one of the data inputs

De-multiplexer: Routes its single input signal to one of the 2n outputs, depending on the values of the N control lines

Comparator: Compares two input words

Clock: A circuit that emits a series of pulses with a precise interval between consecutive pulses

Clock cycle time: The time interval between the corresponding edges of two consecutive pulses

SR Latch: Two inputs, S for setting the latch, and R for resetting (clearing) it.

Key Words – CHAPTER 4

IJVM: Integer Java Virtual Machine, only deals with integers

State: Micro-program set of variables

Opcode: (Operation Code) Identifies the instructions, telling whether it is an ADD, BRANCH, or something else

Data Path: Part of the CPU Containing the ALU, its inputs and outputs

MAR: Memory address register

MDR: Memory data register

MIR: Micro-Instruction Register, a memory data register whose function is to hold the current micro-instruction

Local Variable Frame: For each invocation of a method, an area is allocation for storing variables during the lifetime of the invocation

Operand stack: stacks holding operands during the computation of an arithmetic expression

Constant Pool: Consists of constants, strings, and pointers to other areas of memory

Split cache: separate caches or instructions and data. Benefits of having split cache:

-Memory operations can be initiated independently in each cache, effectively doubling the bandwidth of the memory system.

-Stops average people from writing self-modifying code.

-Can help stop viruses from attacking ALL of your data.

Temporal locality: Occurs when recently accessed memory locations are accessed again

Cache line: Main memory is divided up into fixed size blocks typically consisting of 4 to 64 consecutive bytes

Direct-Mapped Cache: Simplest cache, each row in the cache can hold exactly one cache line from main memory

Cache Hit: The cache entry holds the word being referenced again

Cache miss: The cache entry is invalid or the tags do not match, the needed entry is not present in the cache

WAR dependence (Write After Read): One instruction is trying to overwrite a register that a previous instruction may not have yet finished reading

Key Words – CHAPTER 5

Kernel mode: Intended to run the operating system and allows all instructions to be executed

User mode: Intended to run application programs and does not permit certain sensitive instructions to be executed

General Purpose registers: Hold key local variables and intermediate results of calculations. Their main function is to provide rapid access to heavily used data

PSW (Program Status Word): A control register that is something of a kernel /user hybrid also known as the flag register. Holds condition codes

-N: Set when the result is negative

-Z: Set when the result is zero

-V: Set when the result caused an overflow

-C: Set when the result caused a carry out of the leftmost bit

-A: Set when there was a carry out bit

-P: Set when the result had an even parity bit

Prefix byte: An extra Opcode stuck onto the front of an instruction to change its action

Immediate addressing has the virtue of not requiring an extra memory reference to fetch the operand. The disadvantage is that only a constant can be supplied this way

Direct addressing: The instruction will always access exactly the same memory location so while the value can change the location cannot. Can only be used for global variables

Register Mode: Conceptually the same as direct addressing but specifies a register instead of a memory location

Register indirect addressing: Referencing memory without paying the price of having a full memory address in the instruction using a pointer

Indexed addressing: Addressing memory by giving a register and a constant offset

Base indexed addressing: One register is the base and the other is the index, MOV R4 (R2 + R5) AND R4(R2+R6)

Programmed I/O: Commonly used in low-end microprocessors. Usually have a single input instruction and single output instruction. Spends lots of time waiting

Input driven I/O: Using programed I/O but having an interrupt enable bit in a device register, this way the software can request a signal when the I/O is completed

Direct Memory Access: A chip with direct access to the bus, the chip has (at least) four registers inside it.

Trap: An automatic procedure call initiated by some condition caused by the program, usually an important but rarely occurring condition Ex. Overflow

Trap handler: Performs some appropriate reaction, such as printing an error message. If the result is within range, no trap occurs

Interrupts: Changes in the flow of control caused not by the running program but b something else, usually related to I/O ex: Ricky when its 5 mins to go

The essential difference between Traps and Interrupts is this:

-Traps are synchronous with the program

-Interrupts are asynchronous

Boolean Algebra Review

Law / AND form / OR form
Identity / 1X=X / 0+X=X
Null / 0X=0 / 1+X=1
Idempotent / XX=X / X+X=X
Inverse / XX’=0 / X+X’=1
Involution / (X’)’= X / Same
Commutative / XY=YX / X+Y=Y+X
Associative / (XY)C=X(YC) / (X+Y)+C=X+(Y+C)
Distributive / X+YC=(X+Y)(X+C) / X(Y+C)=XY+XC
Absorption 1 / X(X+Y)=X / X+XY=X
Absorption 2 / X(X’+Y)=XY / X+X’Y= X+Y
Consensus / (X+Y)(X’+C)(Y+C)= (X+Y)(X’+C) / XY+X’C+YC=XY+X’C
DeMorgan’s / (XY)’=X’+Y’ / (X+Y)’=X’Y’

NAND & NOR