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.
  

Data Communication. Introduction

우리는 스마트폰으로 인터넷서핑을 하거나 전화통화, 메일 등의 여러 서비스를 이용하고 있습니다. 이러한 보이지않는 여러 서비스에 상당수가 데이터 통신이랑 연관되어 있는데, 관련 포스트에선 데이터 통신에 대해 다루어보겠습니다. 제가 사용하는 국문 용어가 정식 국문용어랑 많이 다를 수 있는데 조언해주시면 수정하겠습니다.

데이터 통신(Data Communication)

데이터 통신에 대해 정의하기 전에 텔레커뮤니케이션(telecommunication)의 의미에 대해 한번 짚어보면 '원거리 의사소통'으로 간단하게 정의 할 수 있습니다. 그럼 텔레(tele)대신 데이터(data)를 넣으면 바로 데이터 통신(data communication)이 됩니다. 이도 마찬가지로 '원거리에서 데이터를 주고받는 행위'로 설명할 수 있습니다.

데이터 통신의 5가지 구성요소(Five Components)

출처: Data Communications and Networking 5th edition, Forouzan, p 4

• 데이터(Message)
• 송신자(Sender)
• 수신자(Receiver)
• 송수신 매체(Transmission Medium)
  - 데이터(Message)를 전송하기 위한 물리적 통로 혹은 도구
• 규약(Protocol)
  - 데이터 통신에 필요한 규칙들

데이터의 흐름(Data Flow)

• Simplex
  - 단방향 ex) 마이크, 메가폰
• Half-duplex
  - 반 양방향 ex) 무전기
• Full-duplex
  - 양 방향 ex) 대부분의 통신장비

네트워크(Networks)

네트워크는 간단히 정의하자면 통신회선 혹은 매개(communication links) 로 연결되어 있는 기기들의 집합입니다. 여기에서 살펴볼 내용은 네트워크 위상(topology) 의 종류에 대해 다룰겁니다.

• 메시(mesh)

출처: Data Communications and Networking 5th edition, Forouzan, p 10

• 스타(star)

출처: Data Communications and Networking 5th edition, Forouzan, p 10

• 버스(bus)

출처: Data Communications and Networking 5th edition, Forouzan, p 11

• 링(ring)

출처: Data Communications and Networking 5th edition, Forouzan, p 12

이 그림들은 매우 직관적이니

설마 저작권
영어로된 짤이 없어서 아쉽....

네트워크 타입(Network Types)

• LAN (Local Area Network)
  - 소규모 네트워크. 건물이나 작은 구역 내부정도 규모
• WAN (Wide Area Network)
  - 광범위 네트워크. 장거리(도시-도시, 국가-국가)간의 네트워크 지원
• MAN (Metropolitan Area Network)
  - LAN과 MAN사이의 규모 기준이 미국이라 미국의 도시 정도의 규모 (구나 동 정도 규모)

인터넷 (The Internet)

인터넷은 1972년(냉전시대죠) Vint Cerf 와 Bob Kahn 이 개발했습니다. 처음 인터넷이 개발된 목적은 종전의 통신방식의 취약점(전화 같은경우 대부분 star구조이기 때문에 중요거점만 마비되면 전체가 마비됨)을 해소하는 것이었습니다. 이때 당시 프로젝트 이름은 Internetting Project 이었고 이 두사람이 속했던 그룹이 ARPANET그룹입니다.

출처: Data Communications and Networking 5th edition, Forouzan, p 18

   토막상식

• ISP: Internet Service provider
• CBR: Constant Bit Rate (음성 통신)
• DBR: Dynamic Bit Rate (데이터 통신)

프로토콜 과 표준 (Protocols and standards)

프로토콜(Protocols)

• 정의: 데이터 통신이 가능하게 하는 규칙들의 집합
• 기능: 무엇이 언제 어떻게 통신한느지를 정의함

표준(Standards)

• Essential in creating and maintaining an open and competitive market for communications
• Two categories
  - De factor: 표준기관에서 표준을 정하는 방식데로 정해지지 않고, 실제 사용하는 기술이 표준화된 표준 (Ex. WiFi)
  - De jure: 표준기관에서 표준을 정하는 방식에 이거하여 정해진 표준 (Ex. LTE)

표준기관들

• ISO
• ITU-T/ITU-R → 통신 표준기구 (T: tele, R: radio)
• ANSI
• IEEE → layer 1, 2 (WIFI)
• EIA
• 3GPP (Europe) /3GPP2 (US)  → 담당: layer 1, 2 (LTE)
        → 3G가 표준화 될 때 당시에 설립됨 그래서 3G가 들어감
• IETF → 인터넷 프로토콜 담당 (layer 3 혹은 TCP/IP 이상)
• TTA

다음 관련 포스팅에선 OSI-7-Layer 와 TCP/IP의 개념에 대해 다루겠습니다.

Data Communication. OSI-7Layer & TCP/IP

Post outline 

• Protocol Layering 

• OSI Model

• TCP/IP Protocol suite

Protocol Layering

  Layering can be converted to modularization. For example, two peoples communicate through the mail system. 

Ref: Data Communications and Networking 5th edition, Forouzan, p 33

  In this case, each layer just does their's job. Post service just transfer Encrypted mail. This layer doesn't need any other process. Protocol layering is almost same with this example.

  Most important things on this subtopic is 'All of layer communicate peer to peer (same layer to same layer)'.

OSI Model

  The OSI (

Open System Interconnection) model is a layered framework for the design of network systems that allows communication between all types of computer systems. It consists of seven separate but related layers,  each of which defines a part of the process of moving information across a network.

Seven layers of the OSI model
Ref: Data Communications and Networking 5th edition, Forouzan, p 44

  In the past, development for layer 1 and 2 is the main issue, but after that it changes main issue to higher layer development.

These figures are summarized of below the description.

Ref: Data Communications and Networking chapter 2 slide pdf

Ref: Data Communications and Networking chapter 2 slide pdf

Layers description

•   Physical layer

  The physical layer is responsible for movements of individual bits from one hop (node) to the next. + error check
  → make bit by bit connection between sender and receiver.

    Core responsibilities

1. Representation of bits → sending a data
2. Error control

• Data link layer

  The data link layer is responsible for moving frames from one hop (node) to the next.

    Core responsibilities

1. Hop-to-hop (node-to-node) delivery
2. Framing → divide a data to packet
          (layer 1&2: frame,  layer 3: datagram, layer4: packet) 
3. Physical addressing= MAC address
4. Flow control → control the speed of sending and receiving
5. Error control

• Network layer

  The network layer is responsible for the delivery of individual packets from the source host to the destination host.

    Core responsibilities

1. End-to-end (source-to-destination) delivery → find routing path
2. Logical addressing = IP address

• Transport layer

  The transport layer is responsible for the delivery of a message from one process to another.

    Core responsibilities

1. Process-to-process delivery ┓
2. Service-point addressing.    ┛find exact process → use port number 
3. Segmentation and reassembly → decode flexible length of data
4. Connection control → check connecter information then connect.
5. Error control → in the computer hardware, data transmission could occur an error

• Session layer

  The session layer is responsible for dialog control and synchronization.

    Core responsibilities

1. Dialog control → for example, when a telephone call synchronizes voice sending and receiving

• Presentation layer

  The presentation layer is responsible for translation, compression, and encryption.

Core responsibilities

1. Compression and encryption.

• Application layer

  The application layer is responsible for providing services to the user.

    Core responsibilities

1. Providing UI and other functions

TCP/IP Protocol suite

  TCP/IP(Transmission Control Protocol/Internet Protocol) is a protocol suite used in the Internet today. It is a hierarchical protocol made up of interactive modules, each of which provides a specific functionality. 

  The layer in the TCP/IP protocol suite do not exactly match those in the OSI model. The original TCP/IP protocol suite was defined as having four layers: host-to-network, internet, transport, and application. However, when TCP/IP is compared to OSI, we can say that the TCP/IP protocol suite is made of five layers: physical, data link, network, transport, and application. (Look a figure below)

Ref: Data Communications and Networking chapter 2 slide pdf

Difference with OSI-7layer 

1. The protocol is limited (Some of the functionalities of the session layer are available in some of the transport-layer protocols.)
2. It represented only 5 layers (Application layer  is not only one piece of software.)

Summary of address name and packet name

Ref: Data Communications and Networking chapter 2 slide pdf

Data Communication. Introduction

We are using the internet, telecommunication, text messaging and others by smart phone. These invisible services are related to data communication. In related post I will try to describe data communication.

Data Communication

To start with, let's check means of telecommunication. In short, telecommunication is communication at a distance. Then, how about 'data' instead of 'tele'? That would be a data communication. In the same way, data communication is the exchange of data between two devices via some form of transmission medium such as a wire cable.

Five Components

Ref: Data Communications and Networking 5th edition, Forouzan, p 4

• Message
• Sender
• Receiver
• Transmission Medium
  - Path or tools for data (message) transfer.
• Protocol
  - Rules for data communication.

Data Flow

• Simplex
  - Unidirectional as on a one-way street ex) microphone, megaphone
• Half-duplex
  - Each station can both transmit and receive, but not at the same time
  Ex) walkie-talkie
• Full-duplex
  - Both stations can transmit and receive simultaneously ex) telephone

Networks

A network is a set of devices connected by communication links. In here, I just check a network topology.

• Mesh

Ref: Data Communications and Networking 5th edition, Forouzan, p 10

• Star

Ref: Data Communications and Networking 5th edition, Forouzan, p 10

• Bus

Ref: Data Communications and Networking 5th edition, Forouzan, p 11

• Ring

Ref: Data Communications and Networking 5th edition, Forouzan, p 12

I think a more detailed description is useless. So, I will skip it.


Network Types

• LAN (Local Area Network)
  - Small area network. Links the devices in a single office or building.
• WAN (Wide Area Network)
  - Network system for wide area. Provides long-distance transmission.
• MAN (Metropolitan Area Network)
  - This size between LAN and WAN.

The Internet

 In 1972(During the cold war), Vint Cerf and Bob Kahn develop the internet. The goal of the internet reduces the risk of the previous telecommunication system. For example, telephone system use star topology. If star topology's hub broke, all of stations could not do anything. This project was called Internetting Project and both Vint Cerf and Bob Kahn works with ARPANET group.

Ref: Data Communications and Networking 5th edition, Forouzan, p 18

   Tip

• ISP: Internet Service provider
• CBR: Constant Bit Rate (voice communication)
• DBR: Dynamic Bit Rate (data communication)

Protocols and standards

Protocols

• Definition: A protocol is a set of rules that govern data communications
• Role: defines what is communicated, how it is communicated and when it is communicated.

Standards

• Essential in creating and maintaining an open and competitive market for communications
• Two categories
  - De factor: Standards that have not been approved by an organized body, but have been adopted as standards (Ex. WiFi)
  - De jure: Standards that have been legislated by an officially recognized body.
    (Ex. LTE)

Standards Organizations

• ISO
• ITU-T/ITU-R → communication standards organization (T: tele, R: radio)
• ANSI
• IEEE → layer 1, 2 (WIFI)
• EIA
• 3GPP (Europe) /3GPP2 (US)  → layer 1, 2 (LTE)
        → This organization was founded when 3G was developed
• IETF → Takes charge of Internet protocol. Higher than layer 3 or TCP/IP
• TTA

In the next post I will try to describe the concepts of OSI-7-Layer and TCP/IP.

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)