Computer Architecture. chap4 Cache Memory

Cache memory

Overview

I will describe most of the concept of cache by the figure below and just post about L1 cache.

Where is cache?

Example. How to works cache

Assume

 - IR: 16 bit

 - AC: 16 bit = 2bytes = 1word

Steps

1. PC = 300  IR = 1940 Read operation
   Cache state: miss (hit/miss)
2. PC = 301 AC = 003 Read operation
   Cache state: miss
3. PC = 301 IR = 5941 Read operation
   Cache state: hit
4. PC = 302 AC = 0002 → 0005 Read operation
   Cache: hit
5. PC = 302 AC = 0005 → M (941) Write operation

Memory Hierarchy - Diagram

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.139

  This hierarchy goes down the following occur

1. Decreasing cost per bit
2. Increasing capacity
3. Increasing access time
4. Decreasing frequency of access of the memory by the processor
   
   The basis for the validity of condition '4.' is  a principle known as locality of reference (that's why created cache). During the course of execution of a program, memory references by the processor, for both instructions and data, tend to cluster. In short, references to a small set of instructions.

Cache/ Main Memory Structure & Cache Mapping

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.143

  This is an example with some assume. Then, I will add some description about it.

Mapping function  

1. Direct: Have only 1-way. According to the above example, Tag is 6 bits
           →The whole line number appears at address bit. Remainder part is Tag
2. Associative: Have 2^r way. According to the above example, Tag is 14 bits
           →The line number does not appear at address bit. 
3. Set associative: Have k way {k | 1 ~ k ~2^R}.
           →Some of line number appears at address bit.  Remainder part is Tag

Variables summary 

(If you don't have text book(Computer Organization and Architecture 5th edition, William Stallings), ignore it)

• n: address bits
• s: block bits
• r: line bits
• ra: line bits included in the address bits
• w: word bits
• t: Tag bits = s - ra = direct (14 - 8 - = 6) | associative (14 - 0 = 14) 
• k: way

Cache structure = Tag + block

  If a block can be stored in only one line, that means 'one way'  

                                                                               →Direct mapping function

CAM (Content Addressable Memory)

• Compare input with Tags return an address (Line number)
• It has parallel structure, so it returns value immediately.

NOTE

Normally, a memory address is made up by 'byte-addressable' method.

If do something with 'word-addressable' method at same memory, 

LRU(Least Recently Used) replacement

I will just show some figure of LRU.

The components of cache include LRU bit

Details of LRU bit

Locality

• Spatial Locality: refers to the tendency of execution to involve a number of memory locations that are clustered.
• Temporal Locality: refers to the tendency for a processor to access memory locations that have been used recently.

Write Policy

Compare two different styles when memory is shared

Computer Architecture. chap3. A Top-Level View of Computer Function and Interconnection

 A Top-Level View of Computer Function and Interconnection

Computer Components

  I think this figure describes enough.

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.91

Computer Function

  The basic function performed by a computer is execution of a program, which consists of a set of instructions stored in memory.

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.92

  Terms

• Fetch: copy data from memory to IR (Instruction Register)
  - At the beginning of each instruction cycle the processor fetches an instruction from memory
  - The program counter (PC) holds the address of the instruction to be fetched next
  - The processor increments the PC after each IR
• Execute:
  - The processor interprets the instruction and performs the required action
• Opcode: operation code some part of instruction. It refers which operation has to do
• Operand: remainder part of instruction. It refers address

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.93

Example of program fetches and execution

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.93

Interrupts

  Virtually all computers provide a mechanism by which other modules (I/O, memory) may interrupt the normal processing of the processor. (I will almost skip this part)

• Interrupt priority
  
  Interrupt service routine (ISR) → PC ← ISR (to get start address)
                                                                Interrupt Service Routine I(interrupt)RET
• Context Switching
  If certain currently processed job is interrupted, it's information (PC, Accumulator, Registers, SP: stack pointer, etc.) would be stored in memory. Then, process next (which makes interrupt) job → execution → restore interrupted process.

   Class of Interrupt

      - Program

1. Arithmetic overflow
2. Division by zero
3. Attempt execute all illegal machine instruction
4. Reference outside a user's allowed memory space

      - Timer

      - I/O

      - Hardware failure (Ex. Parity error)

       It just checks odd # bit changes in the system → part of the error checking process

Interconnection Structure

DMA (Direct Memory Access)

  DMA moves very simple. DMA process very simple works (Ex. Data copying) without CPU overhead. So, it increases efficiency. If DMA under processing, CPU could not access that devices.

  If several devices request some process at the same time, bus arbiter start process.

Terms

  Arbitration: Because only one unit at a time can successfully transmit over the bus, the arbiter is responsible for allocating time on the bus.

Bus Interconnection

Bus structure

• Data Bus
  - Data lines that provide a path for moving data among system
  - May consist of 32, 64, 128, or more separate lines → combined with word size
• Address Bus
  - Used to designate the source or destination of the data on the data bus
  - Desired word on the address lines
  - Width determines the maximum possible memory capacity of the system
• Control Bus
  - Used to control the access and the use of the data and address lines

     Ex. Address width = 34bit

        

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.108

Synchronous / Asynchronous Bus operation
  Timing refers to the way in which events are coordinated on the bus. Buses to use either synchronous timing or asynchronous timing.

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.113

  Figure 3.18 shows how to process I/O between memory and CPU. At t1, the CPU sends address to check. At  t2, it can work two different ways. One is read from the data. Another one writes to data. I think below figure is looking better.

Read/Write operation  

How to get I/O data

IO mapped I/O & Memory mapped I/O

Memory mapped & I/O mapped

  If you want to know more detail. Please Click here.

Tip

Calculating memory space and word

Ex. 32bit processor → 32bit = 4byte = 1word

     64bit processor → 64bit = 8 bytes = 1word

Ex. 1GB D-Ram

            2^30                 (B) = 1G (B)

   Number of addresses    8 pins for data (memory architecture problem)
If you need more example about real processor Click here.

Computer Architecture. chap2 Computer Evolution and Performance

Evolution and Performance

 First Generation: Vacuum Tubes

  First general purpose electronic digital computer is ENIAC, which designed by using vacuum tubes. (Before ENIAC there is Colossus, but that can not be used general purpose.) It could imagine something like before appear PC at that time people think the computer's appearance and purpose en/decryption, calculation complicated numbers. 

 The Von Neumann Machine

 We can use a PC or laptop or other devices (smart phone, tablet....) very easily and frequently. All of that kind of devices are flowed Von Neumann Machine's concept (Stored program concept). This diagram shows stored program concept. (It's named IAS, because first Von Neumann Machine was named IAS.)

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.40

 Second Generation: Transistors

 After developing transistor, vacuum tubes are replaced by the transistor. Because the transistor is more powerful and efficient than vacuum tubes.

Example) IBM 7094

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.49

 This computer has a CPU, I/O, Memory and especially MUX. MUX work instead of system bus's function. Except MUX, this is similar to recent computer's architecture.

 Third Generation: Integrated Circuits (IC) Later Generation

 Table for comparing performance of the processor

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.59

I think before this processor's table are useless, so I skip that.

Lest's check feature size. Feature size means the minimum line width and if value is smaller, all performances of processor is better (clock speed, energy efficiency, integration rate etc.).

Designing for performance

 On this topic, I will check one thing.
 Built in techniques to be effective for Microprocessor Speed.

• Pipelining
• Branch prediction
• Data flow analysis
• Speculative execution

 Reference (Typical I/O device data rates)

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.62

Multicore

 Every recently produced processors has multicore. Multicore means the multiple processors on the same chip.

The evolution of the Intel x86 architecture
  Let's check some terms and skip this chapter.

• CISC: Complex Instruction Set Computer
• RISC: Reduced Instruction Set Computer

Embedded systems and the ARM
  Definition
  Embedded system: A combination of computer hardware and software, and perhaps additional mechanical or other parts, designed to perform a dedicated function. In many cases, embedded systems are part of a larger system or product, as in the case of an anti-lock braking system in a car.
  ARM: Acorn RISC Machine. A family of RISC- based microprocessors and microcontrollers designed by ARM Inc.

Performance Assessment
 This topic I will use an example.

Clock frequency: 5MHz
Time: τ = 1/f = 1/5M = 0.2μs = 200ns

I1 = 4 cycles → 1.25MIPS

I2 = 6 cycles → 0.833MIPS

I3 = 3 cycles → 1.666MIPS

I4 = 7 cycles → 0.71428MIPS

Terms

• CPI: Cycle per Instruction
• MIPS: Millions of instructions per second

I: Instruction
f: Clock frequency

Summary of Laws

• Moor's law (1965~)
  - The number of transistors that could be put on a single ship was doubling every 18month
  - The cost of a ship has remained virtually unchanged during this period of rapid growth in density.
• Hwang's law (2002~2008)
  - The number of transistors that could be doubling every year.
• Amdahl's law
  - A program running on a single processor such that a fraction (1-f ) of the execution time involves code that is inherently serial and a fraction f that involves code that is infinitely parallelizable with no scheduling overhead.

• Little's law
  - The general setup is that we have a steady state system to which items arrive at an average rate of 入 (Lamda) items per unit time. The items stay in the system an average of W units of time. Finally, there is an average of L units in the system at any one time.
  

Computer Architecture. chap1 Introduction

Today I will post my computer architecture lecture summary (I just undergraduate computer science student.). I will use this blog to post all of my studies. If you have a question or anything else, Just let me know I will respond that as soon as possible.

Intro 
 Definition of some terms
   - Architecture = refers to those attributes of a system visible to a programmer
   - Organization = refers to the operational unit (hard ware)
    It just tip. So, you could ignore this

 Structure and Function
  Structure: The way in which the components are interrelated.
  Function: The operation of each individual component as part of the structure.
   Function(I think these names are easy to understand)

Ref: Computer Organization and Architecture 5th edition,
William Stallings, P.31

• Data processing
• Data storage
• Data movement
• Control

 Structure

Ref: Computer Organization and Architecture 5th edition,

William Stallings, P.32

I think this diagram is easy to understand. This means computer could divide as 4 parts I/O, Main memory, CPU and System bus. Especially, System bus connects all the other devices and makes them could communicate. Other parts are the same style.

This topic don't be hard to understand, but I don't know I explained well....(I'm sorry to my poor English expressions)