Computer System Concept

Chapter 1 : Computer Architecture

1. History of Computer

1.1. Mechanical Era (1600-1940)

1.2. Electronic Era

1.2.1. Generation 1 (1945-1958) ENIAC, IAS

1.2.2. Generation 2 (1958-1964)

1.2.3. Generation 3 (1964-1974)

1.2.4. Generation 4 (1974-present)

1.2.5. Generation 5 (?-?)

2. Computer Performance measurement :

2.1. Memory Bandwidth – bits per second

2.2. MIPS – Million Instruction Per Second (แต่จะ Base on Instruction set ของแต่ CPU ที่ต่างกันด้วย)

2.3. MFLOPS – Million of Floating point operation per second แต่ก็ยัง Base on Instruction set อยู่ดี

2.4. Program for performance analysis

Chapter 2 : The computer system and its interconnection structures

1. ส่วนประกอบหลักของ Computer

1.1. CPU (ALU, Control unit)

1.2. Memories

1.3. I/O devices

1.4. Interconnection structures

2. Von Neumann’s architecture : used the memory of the computer to store the sequence of the control signal manipulations required to perform a task – software programming >> Both data and instructions (control sequence) are stored in a single read-write memory

3. A cycle of instruction execution : Fetch à Decode à Execute à Write back

4. Interrupt : จะเกิดที่ท้าย cycle ทุก instruction เสมอ โดยก่อนที่จะกระโดดไปทำงานตาม Interrupt อื่นที่เข้ามา มันจะต้อง Save ข้อมูลที่อยู่ใน Register เก็บไว้ก่อน ไม่งั้น จะมีข้อมูลอื่นมาทับแทน

5. Interrupt : Processor and OS จะเป็นคนคอยจัดการ recognizing an interrupt, suspending the user program, service the interrupt and then resuming the user program

6. Interrupt : ประโยชน์คือ ทำให้ Performance ดีขึ้น เพราะทำให้ I/O กับ CPU ทำงานพร้อมกันได้ นั่นคือในขณะที่ รอ I/O ทำงานอยู่ CPU ก็จะทำงานอื่นไปด้วย ถ้า I/O เสร็จเมื่อไหร่ก็ค่อยไปบอกให้ CPU มาจัดการต่อ

7. ISR Interrupt Service Routine มีได้หลายตัว แต่ Interrupt signal มันจะมีแค่ตัวเดียว ดังนั้นจึงต้องอาศัย IRQ (Interrupt vector) มากำกับว่าเมื่อเกิด Interrupt แล้วต้องกระโดดไปทำงานที่ ISR ตัวไหน

8. Multiple interrupt กรณีที่มี Interrupt เกิดซ้อนกันมา CPU อาจทำ2แบบนี้คือ อย่างแรก มันอาจไม่สนใจตัวที่มาทีหลังจนกว่าตัวแรกจะเสร็จก่อน หรือ ถ้าตัวที่มาทีหลังมี Priority ที่สูงกว่า มันก็จะหันไปทำงานตัวที่มาทีหลังแทน

9. Priority : การจัด Priority ของ Interrupt ของ I/O device ต่างๆนั้นทำได้2แบบ หลักๆคือ อย่างแรกใช้ daisy chain อย่างที่สองใช้ Interrupt controller

10. Bus interconnection : เป็น Share media , แบ่งเป็น 4 ประเภท Address bus, Data bus, Control bus, miscellaneous bus (power, ground, clock) , Bus performance limit by propagation delay and aggregate demand แก้ไขได้โดยออกแบบเป็น Multiple bus ให้ Bus เร็วๆอยู่ใกล้ๆกับ CPU ส่วน Bus ช้าๆก็ไปต่ออยู่กับ I/O device ที่มี Speed ต่ำๆ เช่น modem

11. Bus arbitration : เป็นกรรมวิธีในการเลือกว่าใครจะได้ใช้ Bus (เพราะ bus เป็น share media จึงต้องผลัดกันใช้) มี2วิธีหลักๆคือ Centralized โดยใช้ Bus controller มาเป็นคนคุม อีกแบบคือ Decentralized จะให้ทุก Device มีส่วนร่วมในการคนใช้ Bus

12. Bus timing : มี 2 แบบ Synchronous คือแบบที่เราใช้กันอยู่ทั่วไป อีกแบบคือ Asynchronous แบบนี้คงมีให้เห็นในอนาคต

13. PC Buses : ISA (8bit , 16bit)

13.1. ISA เป็นแบบ 8bit, 16bit , ต่อได้สูงสุด 4 slot ต่อ 1 ระบบ

13.2. Micro Channel Architecture เป็น IBM proprietary 16 and 32 bit

13.3. EISA (Extended-ISA) 16/32 bit data, 24/32 bit address

13.4. VESA Video Local Bus ใช้ต่อกับการ์ดจอ

13.5. PCI (by intel) 64 bit address 32 bit data

13.6. AGP Accelerator Graphic Port ใช้ต่อกับการ์ดจอ

Chapter 3 : Computer Memory

1. 1 byte = 8 bit , 1 word = ? bit (ขึ้นกับ Instruction set เช่น CPU 32 bit , 1 word = 32 bit)

2. Access technique : มีหลายแบบ Random access , Sequential access, Direct access, Associate access

3. Memory Hierarchy :

3.1. Major design objective : ความจุสูง, เร็ว และไม่แพง

3.2. มี4วิธีที่จะช่วยให้บรรลุวัตถุประสงค์

3.2.1. Use a hierarchy of storage device : เอา Mem หลายๆแบบมาผสมกันให้เป็น 1 memory system

3.2.2. Develop automatic space allocation for efficient use of the memory

3.2.3. Use of virtual memory technique : ใช้ Hard disk มาช่วยทำเป็น Memory

3.2.4. ออกแบบลายวงจรให้มันทำงานได้คล่องและสะดวกมากขึ้น

3.3. Basis of the memory hierarchy

3.3.1. Register internal to the CPU

3.3.2. External storage for data and program

3.3.3. External permanent storage

3.4. Characteristics of the memory hierarchy ตัวที่เร็วๆขนาดเล็กหน่อยราคาสูง จะอยู่ใกล้กับ CPU มากที่สุด ส่วน Memory แบบที่ช้าๆขนาดใหญ่ๆราคาถูกก็จะอยู่ไกลจากตัว CPU หน่อย

3.5. The memory hierarchy works because of locality of reference เอาส่วนที่ใช้บ่อยๆไปเก็บไว้ใน memory ที่เร็วๆเพื่อให้ CPU access ไปใช้ได้เร็วๆ

4. Main memory : มีหลายแบบ

4.1. Core Memory : ใช้ขดลวดกับแม่เหล็ก โดยใช้ขั้วสนามแม่เหล็กเป็นตัวบอกสถานะ bit

4.2. Semiconductor memory (typically random access)

4.2.1. RAM (Dynamic RAM, Static RAM)

4.2.2. ROM (ROM, PROM, EPROM, EEPROMS, Flash memory

4.3. Improvement to DRAM โดยเอา cache เข้ามาช่วย cache ทำจาก SRAM ที่เร็วกว่าแพงกว่า DRAM โดยเอา cache มาประกอบเข้ากับ DRAM อาจจะแค่ 1 line หรือ Multi line เพื่อช่วยให้ CPU access memory ได้เร็วขึ้น เพราะ CPU จะมา access ที่ cache แทน

5. Error correction ใช้สูตร 2^K-1 > M+K เพื่อคำนวณหาค่าจำนวน K bit ที่จะเพิ่มขึ้นมาเพื่อทำ Error correction ให้กับ Data ขนาด M bit เช่น Data ขนาด 8 bit ต้องใช้ K=4 à 2⁴-1 > 8+4 à 15 > 12

6. Cache Memory : เล็กกว่า แพงกว่า เร็วกว่า Main memory ทำงานโดย Copy ข้อมูลจาก Main memory มาเก็บไว้ (ไม่ใช่การ move) ที่เหลืออ่านชีทเอง เพราะเป็นเรื่องที่ยุ่งพอควร

7. External Memory :

7.1. Magnetic Disks :

7.1.1. มีการแบ่งเป็น Track, Sector โดย Track คือการแบ่งเป็นวงรอบ ส่วน Sector คือการแบ่งวงรอบตามมุมรัศมี เหมือนการแบ่งพิซซ่านั่นแหละ

7.1.2. ส่วนขั้นตอนการอ่านข้อมูลจะเริ่มหา Syn byte ให้เจอก่อน เพื่อเป็นตัวบอกว่านี่เป็นจุดเริ่มต้น จากนั้นเช็ค Gap ที่คั่นกลางอยู่เรื่อยๆเพื่อเป็นตัวบอกว่าข้อมูลอยู่ตรงไหน

7.1.3. Data access time

7.1.3.1. Seek time เวลาเคลื่อนหัวอ่านจนเจอ track ที่ต้องการ

7.1.3.2. Rotational latency เวลารอจนเจอ Sector ที่ต้องการ

7.1.3.3. Access time = Seek time + Rotational latency

7.1.3.4. Block transfer time : time to read the block (Sector) off of the disk and transfer it to main memory

7.2. RAID technology คือ Concept การสร้าง Parallel disk

7.2.1. RAID 0 ใช้วิธีแบ่งข้อมูลเป็น Block, strip (1 Block มีหลาย Strip) แล้วกระจายข้อมูลไปใน Disk หลายๆตัว RAID0 จะทำให้มี High transfer rate แต่ยังไม่มี Redundant

7.2.2. RAID1 มี Redundant โดยการทำ Disk mirror ข้อเสียคือแพงเพราะใช้ Disk จำนวนมาก

7.2.3. RAID2 ต้องการลดจำนวน Disk จาก RAID 1 ลง โดยใช้วิธี CRC แทน แล้วเก็บค่า CRC ไว้ใน Disk ซึ่งจะใช้จำนวน Disk น้อยกว่าการทำ Mirror แต่ก็ลดลงได้นิดหน่อย

7.2.4. RAID3 ต้องการลดจำนวน Disk ลงอีกก็เลยเปลี่ยนจาก CRC มาใช้ Parity bit แทน

7.2.5. RAID4 ต้องการเพิ่มประสิทธิภาพจาก RAID3 ดังนั้น RAID4 จึงไม่ทำ parity แบบ bit per bit แต่จะทำแบบ Block per Block นั่นคือมันจะอ่าน Parity block ก็ต่อเมื่อพบว่ามี error เกิดขึ้นเท่านั้น

7.2.6. RAID 5 ต้องการเพิ่มประสิทธิภาพจาก RAID4 เพราะ Disk ที่เก็บ Parity ทำงานหนักเกินไป ก็เลยกระจายให้ Parity กระจายอยู่ตาม Disk ต่างๆ

7.3. Optical disk

7.3.1. CD is operated using constant linear velocity

7.3.2. CD เวลาสร้างจะต้องใช้ Master Disk เป็นแม่พิมพ์ปั๊มแผ่นลูกๆออกมา

7.3.3. CD-R จะเขียนได้ครั้งเดียว โดยการยิงแสงเลเซอร์ไปเผาพื้นผิวเป็นจุดๆ เพื่อเปลี่ยนทิศการหักเหของแสง

7.3.4. CD-RW แบบนี้จะเขียนลบได้หลายครั้ง

7.3.5. Magneto Optical Disk เป็นแผ่นแม่เหล็กแสง คือใช้แสงเลเซอร์ไปเผาพื้นผิวให้ร้อนจนทิศสนามแม่เหล็กบนพื้นผิวเปลี่ยนทิศทาง เพื่อเป็นการเก็บสถานะ bit ที่ต้องการ

7.4. Magnetic Tape ราคาถูกมากแต่ก็ช้ามากเช่นเดียวกัน เป็น Sequential access

Chapter 4 : Input / Output

1. External devices are not generally connected directly into the bus structure of the computer แต่จะมี I/O module ที่มีมาตรฐานเป็นกลางมาคั่นกลางระหว่าง Bus กับ I/O devices

2. The I/O module : Provide a standard interface to the CPU and the bus

3. Interface consist of : Control, Status and Data signal ทั้ง3 อย่างนี้คือมาตรฐานที่จะใช้ในการต่อกับ I/O device ที่มาจากบริษัทร้อยพ่อพันแม่ที่เป็นเจ้าของ I/O device ต่างๆ

4. Programmed I/O : การทำงานแบบนี้ จะมีการ Provide standard interface ให้กับ CPU แต่ CPU จะต้องมานั่งคุม device เองตลอด ซึ่งจะทำให้ระบบทั้งหมดช้าลงตามความเร็วของ I/O เพราะ CPU มานั่งคุมอยู่ตรงนี้ ไม่ได้ไปทำงานอื่น ข้อดีจะมีก็แค่การมีมาตรฐานการเชื่อมต่อ I/O device ให้กับ CPU ก็เท่านั้นเอง

5. I/O addressing : แบบนี้จะใช้การอ้างถึง I/O address กับ Memory แยกจากกัน แล้วออกแบบ instruction set ให้ชัดเจนว่าอันไหนใช้กับ I/O สำหรับการที่จะรู้ว่าเมื่อไหร่อ้างถึง Memory หรือ I/O ก็จะใช้สัญญาณ Chip enable มาช่วยเลือก ข้อเสียคือทำให้ Real memory address ลดลง แต่ในปัจจุบันก็ไม่ใช่ปัญหาใหญ่ เพราะ real address memory ใหญ่มากๆ เพราะฉะนั้นเสียไปนิดหน่อยก็ไม่เป็นไรนัก

6. Interrupt-Driven I/O : แบบนี้จะช่วยลดเวลาที่ CPU ต้องมานั่งคุม I/O โดยมีขั้นตอนหลักๆดังนี้ CPU สั่งงาน I/O , CPU กลับไปทำงานอื่นต่อ , I/O ทำงานต่อเองจนเสร็จ และเมื่อเสร็จแล้วก็ขอ Interrupt ไปยัง CPU , CPU หันมาดู I/O ที่บอกว่าเสร็จแล้วเพื่อปิดงาน จากนั้นก็หันไปทำงานอื่นต่อเหมือนเดิม

7. Direct Memory Access (DMA) : จะเข้ามาช่วยตอนที่ CPU ต้องถ่ายโอนข้อมูลจาก I/O ไปยัง Memory โดยปกติการถ่ายโอนแบบปกติ ก่อนจะถ่ายโอนข้อมูล 1 word ต้องมีคำสั่ง Initial ส่งเสร็จก็ต้องมีคำสั่ง Finish ว่าจบ แล้วถ้าจะโอนข้อมูล 1000 word เราก็จะเปลืองเวลาการ Initial มาก DMA ก็เลยจะมาช่วยลดสิ่งเหล่านี้ โดยจะทำการ Initial ครั้งแรกครั้งเดียว จากนั้นการส่งข้อมูลจะกี่ word ที่ตามมาก็ไม่ต้อง Initial อีกจนจบ ซึ่ง CPU ก็ไม่ต้องมานั่ง Initial อยู่ตลอด CPU ก็ไปทำงานอื่นได้ Performance ก็จะดีขึ้นอีก

8. การใช้ Bus เพื่อส่งข้อมูลระหว่าง I/O กับ Memory นั้นมีสองวิธี

8.1. รอจังหวะที่ไม่มีคนอื่นใช้ Bus เช่นช่วง exec, decode แล้วก็แอบใช้ Bus ในจังหวะนั้นส่งข้อมูล

8.2. บังคับใช้ Bus เลย คือพอจะส่งข้อมูลก็บอกให้คนอื่นที่จะใช้ Bus ด้วยรอก่อนแป๊ปนึง แล้วก็ส่งข้อมูล จากนั้นค่อยผลัดให้ คนอื่นได้ใช้ Bus

9. External Interface : จะต้องมีการกำหนดรูปแบบการส่งข้อมูลว่า

· Parallel or serial data transfer

· Data format conversions

· Transfer rates

· Number of devices supported

· ตัวอย่างเช่น RS232 serial port, Game port, SCSI, USB, P1394

Chapter 5 : The Operating System

1. Operating System : Is program that manages the resources, provides services to programmer, schedules execution of other programs, mediates programmer and application programs requests for facilities and services

2. Services provided : Program creation, Program execution, Standardized access to I/O devices, Controlled access to files, Overall system access control

3. Types of O/S : Interactive, Batch, Multiprogramming / time sharing

4. Scheduling : กรณีของ multiprogramming จะทำงานได้จะต้องมี Scheduling เป็นคนคอยจัดการให้โดยแบ่งเป็น 3 ด้าน

4.1. High level scheduling : จะดูว่าเครื่องมี Resource พอหรือไม่ ถ้าพอก็จะจองไว้ให้แล้วโหลดโปรแกรมลง Memoryให้

4.2. Short term scheduling : จะเป็นส่วนที่จะเลือกว่าโปรแกรมตัวไหนที่อยู่ใน queue ที่จะถูกรัน โดยจะดูจาก status ของโปรแกรม ซึ่งมีดังนี้ New, Ready, Running, waiting, halted

4.3. I/O : เป็นส่วนที่ดูแล I/O ที่รออยู่ใน queue

5. จุดอ่อนที่ Scheduling มีอยู่คือ มันจะพยายามโหลดโปแกรมลง memory ให้มากที่สุดเท่าที่จะทำได้ แต่พอทำงานจริงกับปรากฏว่ามีโปรแกรมที่หยุดชั่วขณะ หรือตัวที่ต้องรอการทำงานของ I/O อยู่ใน memory สิ่งเหล่านี้ทำให้การใช้งาน memory ไม่มีประสิทธิภาพ เพราะแทนที่จะเป็นที่อยู่ของตัวที่ต้องทำงานจริงๆ แต่กัยไปเป็นที่อยู่ของพวกที่หยุดรอคนอื่นๆแทน เขาก็เลยมี memory management มาช่วยแก้ปัญหานี้ให้

6. Memory management : Idea หลักคือย้ายตัวที่หยุดรอหรือไม่ได้ทำงานออกนอก memory ไปเก็บไว้ใน Intermediate queue แล้วเอาตัวที่มี status ready พร้อมที่จะรันจริงมาไว้ใน memory แทน วิธีการแบบนี้เราเรียกว่าการทำ swapping

7. การย้ายโปรแกรมมาใส่ใน memory ก็ต้องมาดูเรื่องพื้นที่ที่จะลง นั่นคือ partition ซึ่ง partition มีอยู่ 2 แบบคือ Fix size และแบบ Variable size มาถึงตอนนี้เราก็สามารถ swap โปรแกรมเข้าออก memory ได้แล้ว แต่ก็ติดปัญหาเรื่องการอ้างอิง address อีก คือ เวลาโปรแกรมทำงานมันจะใช้ Program address หรือ logical address ในการทำงาน แต่พอเรา swap โปกแกรมเข้าออก memory จะพบว่า physical address มันไม่ได้เรียงกันอย่างต่อเนื่อง เพราะเราสลับไปมาตามแต่ว่าพื้นที่ไหนว่างก็จับใส่ลง ดังนั้น จึงต้องมีกลไกในการช่วย convert ระหว่าง logical address และ physical address ให้เข้าใจตรงกัน วิธีที่ว่าก็คือการทำ Paging นั่นเอง

8. Paging : จะใช้ page table ในการช่วย map ระหว่าง Physical address กับ Logical address

9. Virtual Memory : คือการใช้ Hard disk มาช่วยทำเป็น memory โดยมี idea ว่าส่วนไหนของโปรแกรมที่รันอยู่บ่อยๆก็ให้เก็บไว้ใน memory ส่วนไหนที่ไม่ค่อยได้ใช้ก็เก็บไว้ใน Hard disk โดยที่ยังให้มองเสมือนว่า เป็น memory ก้อนเดียวกันทั้งหมด จึงมีการใช้ Page table มาช่วยเพื่อบอกว่าตอนนี้ส่วนไหนอยู่ใน Mem ใน HD แต่ปัญหาที่ตามมาอีกคือถ้าโปรแกรมที่ใหญ่มากๆก็จะมี Page table ที่ใหญ่ตามไปด้วย ซึ่งก็จะกลายเป็นปัญหาตามมาอีก จึงต้องมีวิธีลดขนาด Page table ลง

10. การลดขนาด Page table ทำได้ 2 แบบหลักๆคือ

10.1. Using a 2-level page table คือใช้ first level table เก็บ index ของ second level table ที่เก็บที่อยู่จริง

10.2. Use an inverted table structure มี 1 table ที่ support ทุกโปรแกรม โดยใช้ hash function ในการ map หา page request

11. จากข้อ 10 จะเห็นว่าเราต้อง access page table ก่อน แล้วค่อย access memory จริง ซึ่งต้องเสียเวลา ก็เลยเอา cache มาช่วยเก็บ table information โดยเฉพาะ เพื่อให้ access เร็วขึ้น ซึ่งเราเรียก cache นี้ว่า TLB (Translation lookaside buffer)

12. เมื่อจะโหลดโปรแกรมลง memory ต้องดูก่อนว่ามีที่ว่างหรือไม่ ถ้ามีก็ Ok ไป แต่ถ้าไม่มีก็ต้องย้ายบางตัวออก ซึ่งตอนย้ายก็ต้องมีกรรมวิธีในการ Update ข้อมูลไปลง HD ไว้ก่อน ซึ่งวิธีก็จะใช้แบบเดียวกับที่ทำใน Cache คือมี 3 แบบ LRU, FIFO, Random

13. Segmentation : ในกรณีที่มีหลายๆโปรแกรมต้องการ Share Page ร่วมกัน ถ้าใช้ Paging ธรรมดาก็จะลำบากหน่อย เพราะแต่ละโปรแกรมเหมือนแยกกันอยู่คนละโลกไม่เชื่อมถึงกัน เพราะมี Page table แยกจากกัน วิธีแก้คือ Segmentation

Chapter 6 : CPU Arithmetic

1. ALU : performs arithmetic and logical operations on data, all other elements of the computer system are there mainly to bring data to the ALU for processing

2. 2 Basic component : are required to produce a fully functional ALU

· A bit-wide full adder unit

· A 2-input NAND gate

3. Integer Representation :

3.1. Sign-magnitude format : ใช้ bit ซ้ายสุดเป็นตัวบอกว่าเป็นบวก(0)หรือลบ(1)

3.2. Ones complement format :

3.3. Twos complement format : สองอันนี้ให้ดูรายละเอียดในชีทเอง (อย่าลืมแยกให้ออกระหว่างความแตกต่างของ two complement format กับ two complement operation)

4. การบวกลบคูณหาร ให้ดูรายละเอียดในชีทจะสะดวกกว่า

Chapter 7 : Instruction set

1. Each instruction must contain 4 basic information :

1.1. Operation code : คำสั่งที่จะทำคืออะไร

1.2. Source operand references : operand ที่จะใช้คืออะไร

1.3. Result reference : ผลลัพธ์เก็บที่ไหน

1.4. Next instruction reference : คำสั่งต่อไปอยู่ที่ไหน

2. Five categories of instructions

2.1. Arithmetic operation

2.2. Logic operations

2.3. Data movement (internal to the system)

2.4. I/o (Data movements between the computer and external devices)

2.5. Control operations

3. RISC : จำนวน instruction ต้องให้มีน้อยที่สุดและเล็ก และจำนวน clock ที่ใช้แต่ละตะวต้องเท่ากัน และสามารถประกอบเป็นคำสั่งต่างๆกันได้

4. CISC : จำนวน instruction มากเพื่อสะดวกต่อ user โดยจะ base on memory ที่ใช้เก็บ micro instruction อีกที (แบบนี้อาจจะใช้กว่า RISC แต่จะง่ายต่อ user)

5. Address in an instruction : มี 4 แบบหลักๆ

5.1. 3 address instruction เช่น x=y+z , SUB Y,A,B

5.2. 2 address instruction เช่น x=x+y , MOV Y,A

5.3. 1 address instruction เช่น Acc=Acc+x LOAD D

5.4. 0 address instruction เช่น TBA (transfer register B to A)

6. Control operation : เช่น Branch, Skip, Subroutine call/ return

7. Endian war :

· Big endian : stores most significant byte in the lowest address (เก็บเหมือนที่คนอ่านตามปกติ) CPU ที่มาจาก motorola มักใช้แบบนี้

· Little endian : stores the word in reverse คือจะเก็บตรงข้ามกับ big endian CPU จาก Intel มักเป็นแบบนี้

· ปัญหาที่ตามมาคือ เวลาจะโอนข้อมูลข้ามถึงกันก็ต้องมีตัวทำ format conversion ไม่งั้นก็จะคุยกันไม่รู้เรื่อง

8. Addressing Modes :

8.1. Immediate mode : ADD A,5 บวก A ด้วย 5

8.2. Direct mode : ADD A,(5) บวก A ด้วยค่าที่อยู่ใน address 5

8.3. Indirect addressing : ADD A,((5)) บวก A ด้วยค่าที่ address 5 บอกที่เก็บ address ที่บอกที่เก็บข้อมูล

8.4. Register-based addressing modes เหมือน3อันแรก แต่เป็นการกระทำกับ register แทน

8.5. Displacement or address relative addressing ใช้ 2 address คือ base address และ relative address

8.6. Indexing

Chapter 8 : the CPU structure

1. 4 Cycles of CPU : Fetch instruction , Fetch data , Process data , Write data

2. การจะทำงานตามข้อ 1 ได้ต้องอาศัยสิ่งเหล่านี้ : ALU, Control unit, Register

3. Register organization :

3.1. มีขนาดเล็ก จำนวนน้อย แต่เร็วสุดๆ

3.2. มี 2 type

3.2.1. User visible : แบบนี้ user สามารถมองเห็นและนำมาใช้งานได้

3.2.2. Control and status register : แบบนี้ user มองไม่เห็น และเอามาใช้งานไม่ได้

4. User-visible registers : มีหลายแบบ

4.1. General purpose : เอาไว้ใช้งานทั่วไป เก็บอะไรก็ได้

4.2. Data : ใช้เก็บได้แต่ data อย่างเดียว

4.3. Address : ใช้เก็บได้แต่ address อย่างเดียว

4.4. Condition code : ถูก set โดย CPU à User มองเห็น แต่แก้ไขอะไรไม่ได้

4.5. ถามว่าขนาด Register ควรกว้างเท่าไหร่ดี : ตอบว่าเอาแค่กว้างพอที่จะรองรับขนาด Architecture CPU ได้ก็พอ นั่นคือ CPU 32 bit ก็ใช้ register ขนาดกว้าง 32 bit ก็พอ ไม่ต้องถึงขนาดกว้าง 64 bit

5. Control and status registers : เช่น PC, IR, MAR, MBR, program status word

6. Instruction cycle : Fetch the instruction à Decode it à Fetch operands à Perform the operation à store results à recognize pending interrupts ทั้งหมดนี้ต้องขึ้นกับแต่ละ CPU ด้วย เพราะอาจแตกต่างกันได้ตามชนิดของ CPU

7. Instruction Pipelining : to divide a task into K independent sequential subtasks, each subtask requires 1 time unit to complete, The task itself then requires k time units to complete

8. For n iterations of the task :

· With no pipelining : nk time unit

· With pipelining : k + (n-1) time units

· So, Speed up S= nk / [k+(n-1)]

9. Speed ของ Pipeline จะขึ้นกับ Stage ที่ทำงานช้าที่สุด

10. กรณีที่เจอ branch มันจะต้อง Flush สิ่งอยู่ใน Pipeline ออกให้หมดให้เป็น empty แล้วเริ่มโหลดเข้ามาใหม่ ซึ่ง Pipeline ที่มี stage เยอะๆ ก็จะใช้เวลา flush นานกว่าแบบที่ pipe สั้นกว่า

11. เราสามารถเพิ่ม ALU เข้ามาใน CPU ให้ทำงานขนานกัน เพื่อช่วยเพิ่ม efficiency ขึ้น แต่ก็ต้องระวังเรื่อง dependency ด้วย ที่อาจทำให้ข้อมูลผิดได้

12. Pipeline Limitation :

12.1. Pipeline Depth : ทั้งนี้มันจะมี delay ของ buffer ที่ใช้คั่นแต่ละ stage เพราะงั้นยิ่ง stage มาก delay ยิ่งมาก แถมต้องมีวงจรควบคุม buffer เหล่านี้ด้วย เราจึงทำให้มันลึกมากๆไม่ได้

12.2. Data dependencies : ถ้าออกแบบไม่ดีทำให้แต่ละ stage เกิด data dependency ขึ้นจะทำให้ข้อมูลผิดได้ และถ้า stage มีมากไปก็มีโอกาสเกิด data dependency ได้ง่ายด้วย

12.3. Branching : พอเจอ branch ก็ต้องมีการ flush แล้วเริ่มใหม่ สิ่งเหล่านี้หลีกเลี่ยงไม่ได้ แต่ก็พอมีวิธีช่วยลดผลกระทบของการต้องโหลดใหม่อยู่บ้างดังนี้

12.3.1. Multiple streams : ก็ทำ duplicate ช่วงก่อน execute เป็น 2 เท่าเลย เพื่อ parallel branch รอไว้

12.3.2. Prefetch branch target : พอมันเจอ branch (แต่ยังไม่แน่ใจว่าจะ jump ไปหรือไม่ )มันก็จะ Prefetch มาเก็บไว้ใน high speed memory แล้วรอ ถ้าไม่ Jump ก็แล้วไป แต่ถ้า Jump มันก็จะ Flush และโหลดตามปกติ แต่จะดีหน่อยตรงที่ทำกับ high speed memory แทน ไม่ต้องไปทำกับ low speed memory เพราะงั้นก็ช่วยลดเวลามาได้หน่อย

12.3.3. Look ahead, look behind buffer (loop buffer) : คือไปขยาย buffer ให้ใหญ่มากพอจนเก็บ Instruction ที่จะวนลูปได้ทั้งหมด เพราะงั้นเวลาเจอ branch มันก็จะกระโดดไปมาใน buffer นี้แหละ ก็จะทำให้เร็วขึ้น ไม่ต้องไปยุ่งกับพวก low speed memory (ใช้ concept ของ cache แต่ใช้เฉพาะกับ branch)

12.3.4. Branch prediction : แบบนี้พยายามจะลด Flush ให้เหลือน้อยที่สุด โดยพยายามจะทาย Branch ที่จะไปล่วงหน้าแล้วโหลดมารอเลย วิธีนี้ขึ้นกับความถูกต้องการเดาว่าจะมากน้อยแค่ไหน ซึ่งการเดาก็มี 2 แบบหลักๆคือ Static guesses และ Dynamic guesses

12.3.5. Delayed branch : แบบนี้พยายามจะลด Flush ให้เหลือน้อยที่สุด โดยอาศัยความสามารถของ compiler โดยพยายาม compile ให้โปรแกรมมีคำสั่งที่ถูกลำดับส่งไปให้ CPU รันเสมอ เพื่อไม่ให้เกิดการ flush โดย compiler จะคำนึงถึงเรื่อง data dependency ร่วมด้วยเสมอ

13. Superpipeline design : พยายามออกแบบให้ Pipeline มี stage ที่มากขึ้น ใช้ clock ที่เร็วขึ้นเพื่อให้ระบบทำงานได้เร็วขึ้น

14. Superscalar design : พยายามออกแบบให้มีส่วน Operate มากกว่า 1 ตัว เช่นมี ALU 2 ชุด มี Pipeline 2 ชุด เพื่อให้ทำงานขนานกันจะได้เร็วขึ้น

15. Superscalar design Limitation :

15.1. Data dependencies

15.2. Resource dependencies

15.3. Instruction issue policy

· In-order issue, in-order completion วิธีนี้ธรรมดา ช้า

· In-order issue, out-of-order completion วิธีนี้ต้องระวังเรื่อง Output dependencies ด้วย

· Out-of-order issue, out-of-order completion วิธีนี้ต้องระวังเรื่อง Antidependence

15.4. Register renaming เพ่อแก้ปัญหา Output dependencies , Antidependence

15.5. Impact on machine parallelism

· การเพิ่มแต่ ALU โดยไม่มีการทำ Register renaming มา support จะทำให้ performance ถูกจำกัดด้วยเรื่องของ data dependencies

· Out-of-order issue จะเกิดประโยชน์สูงถ้ามี instruction buffer windows ที่ใหญ่ๆ

Chapter 10 : Control Unit Overview

1. แต่ละคำสั่งของ CPU นั้นจริงๆแล้วประกอบด้วยการทำงานแบบ Serial ของ microoperations ซึ่งจะถูกควบคุมโดย Control unit อีกที

2. Control Unit : หน้าที่คือ

2.1. Define ว่า element ไหนของ CPU ที่จะต้องทำงานร่วมกัน (Select element)

2.2. Define microoperation ไหนที่จะให้ CPU ทำ (Select function)

2.3. คุม Sequence การทำงาน (Data flow)

3. Microoperations : เป็นหน้าที่การทำงานเล็กๆที่สามารถประกอบเป็น 1 คำสั่งของ CPU ได้ ซึ่งจะถูกควบคุมการทำงานโดย control unit การสร้าง microoperation มี 2 แบบหลักๆ

3.1. Hardwired logic : เล็ก เร็ว แต่ modify ได้ยาก อาจถึงรับต้องออกแบบใหม่เลยถ้าจะแก้ไขมันนิดหน่อย พวกนี้จะเห็นใน RISC เป็นส่วนใหญ่

3.2. Microprogrammed control unit : คำสั่งเล็กๆจะเก็บใน memory เฉพาะของมัน ซึ่งเราสามารถเขียนโปรแกรมเล็กๆสั่งการทำงานไว้ในนี้ได้ ทำให้การ modify ทำได้ง่าย แต่จะมีขนาดใหญ่กว่าและช้ากว่าแบบ RISC

4. Hardwired approach : Three general design approaches

4.1. Traditional “state-stable” method from a digital logic course

4.2. Clocked delay element

4.3. Sequence counter approach

5. Microprogramming : ใน control unit จะมี memory เอาไปเก็บ microprogram เลย เรียกว่า micro code (เก็บ data ที่จะเอาไปคุม switch)

6. Vertical microprogramming : each micro instruction specified a single (or few) microoperations to be performed

7. Horizontal microprogramming : each micro instruction specified many different microoperations to be performed in parallel

8. Compromise : จะใช้ผสมกันทั้งแบบ Vertical และ Horizontal โดยเอากลุ่มที่มีโอกาสเปิด(switch)พร้อมกันมาอยู่ Horizontal แต่ถ้าเปิดไม่พร้อมกันก็ใช้แบบ vertical

9. Second compromise : nanoprogramming

9.1. Use a 2-level control storage organization

9.2. Top level is a vertical format memory

· Output will drives the address register of the bottom (nano-level) memory

9.3. Nanomemory uses the horizontal format à produce the actual control signal outputs

9.4. ข้อดีของวิธีนี้คือช่วยลดขนาด Control memory ลง

9.5. ข้อเสียคือซับซ้อนมากขึ้นทำให้ช้าลง

9.6. nanoprogramming มีใช้กันมากใน CISC microprocessors

เพิ่มเติม

Cache memory

1. คุณสมบัติของ cache : เล็ก (แต่ต้องใช้เป็นตัวแทน RAM ขนาดใหญ่ได้) เร็ว (เพราะใช้เทคโนโลยีการผลิตเดียวกับ CPU) แพง (เพราะสร้างจาก SRAM ไม่ใช่ DRAM ถูกๆ)

2. การทำงาน :

2.1. เราจะ Transfer ข้อมูลจาก RAM (Memory นั่นแหละแต่ในที่นี้จะเรียกว่า RAM นะจะได้เห็นภาพชัด) มาเก็บ (Copy นะไม่ใช่ Cut and paste) ไว้ใน Cache ที่ละ block โดยที่เมื่อเอามาเก็บใน Cache แล้วเราจะเรียก block นั้นว่า line หรือ line แทน (แค่เปลี่ยนชื่อเฉยๆ แต่ขนาดยังเท่าเดิม) นั่นคือ Cache ประกอบด้วยหลายๆ Line (หรือใส่ได้หลายๆ block นั่นเอง) (ใน 1 block หรือ line จะใส่ข้อมูลได้อีกหลาย word )

2.2. CPU จะมองไม่เห็น RAM จะเห็นก็แต่ cache มันก็เลยจะทำงานเฉพาะกับ Cache เท่านั้น โดยมันจะ ทึกทักเอาเองว่าข้อมูลทั้งจักรวาลอยู่ที่ Cache นี่แหละ แต่ถ้ามันไม่มีจริงก็เป็นหน้าที่ Cache controller เองที่จะต้องไปหามาใส่ไว้ใน Cache โดย CPU มันจะไม่สน

2.3. ประเด็นที่ต้องสนใจในการออกแบบ cache คือ

2.3.1. Mapping function เพื่อให้ Cache ขนาดเล็กสามารถเป็นตัวแทน RAM ขนาดใหญ่ๆได้

2.3.2. Line replacement เพราะขนาดที่เล็กของ cache ก็เลยต้องมีการ swap ข้อมูลเข้าๆออกๆบ่อยๆ ก็เลยต้องมีกติกาการ swap ด้วยว่าจะทำอย่างไร

2.3.3. Write policy : จำได้ไหม cache controller จะ copy ข้อมูลจาก RAM มาเก็บใน cache มันก็เลยกลายเป็นว่าข้อมูลมี 2 ที่คือ ใน RAM, cache ก็เลยต้องพูดเรื่องนี้เพื่อป้องกันข้อมูล 2 ที่มีค่าแตกต่างกัน ไม่งั้นเดี๋ยวมั่ว

2.3.4. Block Size : แล้วขนาด Block หรือ Line ควรใหญ่เล็กเท่าไหร่ดีล่ะ อืมมมน่าคิด

2.3.5. Number and type of cache อืมมมนี่ก็น่าคิดว่าเอาไงดี

3. Mapping Function : มี 3 แบบใหญ่ๆ

3.1. Direct mapping : ใช้วิธีล็อกไปเลยว่า Block ที่เท่าไหร่ใน RAM มีสิทธิ์ไปอยู่ใน Line ไหนใน cache ได้ แล้วอาศัยการเปรียบเทียบ tag ว่าตรงกันหรือไม่ระหว่าง address ที่ต้องการหา กับ tag ที่เก็บใน cache แบบนี้ง่ายดีแต่ไม่ค่อยยืดหยุ่น

3.2. Associative mapping : แบบนี้พยายามจะให้ยิดหยุ่นมากขึ้น ก็เลยไม่กำหนดตายตัวว่า Block ไหนลง line ไหนได้ แต่จะให้ลงได้อิสระเลย โดยใช้วิธีเทียบกับ tag เอากับทุก line ใน cache พร้อมกัน (Parallel) ว่าตรงกับตัวไหน วิธีนี้เสียที่ว่าต้องเสียพื้นที่เก็บ tag ใหญ่มาก เมื่อเทียบกับพื้นที่ที่ใช้เก็บข้อมูลจริง

3.3. Set associative mapping : แบบนี้จะเป็นลูกผสมระหว่าง 2 แบบข้างบน โดยจะมองว่า มีหลาย line ประกอบกันเป็น set (ถ้า 1 set มี 4 line จะเรียกว่า 4-way) และ หลายๆ set ประกอบเป็น cache แล้วใช้วิธี Direct mapping กระทำกับ set จากนั้นพอจะเลือก line ก็ใช้วิธี Associative mapping โดย compare tag ของทุก line ว่าตรงกับตัวไหน พอเจอ line ที่ต้องการ ก็ค่อยใช้ word offset เลือกเอา word ที่ต้องการ

4. ตัวอย่างการคำนวณ : โจทก์ ว่า มี RAM ขนาด 1M byte (เพราะฉะนั้นก็จะรู้ว่า address มีขนาด 20 bit ) แล้ว cache มี 1K line แต่ละ line แต่ละ line เก็บข้อมูลได้ 8 bytes (เพราะฉะนั้นก็จะรู้ว่า word offset ใช้ 3 bits นะ)

4.1. Direct mapping จาก address ขนาด 20 bits จะแบ่งได้เป็น

· Word id (หรือ word offset) = 3 bits

· Line id = 10 bit (เพราะ cache มี 1K line เพราะงั้นเลยต้องใช้ 10 bit มา code)

· Tag id = 7 bits (ที่เหลือคือ 20-3-10 = 7)

· Ex : address ABCDE = 1010 1011 1100 1101 1110

แบ่งใหม่ตามจำนวน bit = 101 0101 11 1001 1011 110

นั่นคือ tage = 55

Cache line = 39B

word offset = 6

4.2 Associative mapping จาก address ขนาด 20 bits จะแบ่งได้เป็น

· Word id (หรือ word offset) = 3 bits

· Tag id = 17 bits (ที่เหลือคือ 20-3 = 17)

· Ex : address ABCDE = 1010 1011 1100 1101 1110

แบ่งใหม่ตามจำนวน bit = 1 0101 0111 1001 1011 110

นั่นคือ tage = 1579D

word offset = 6

4.3 Set associative mapping : แก้โจทก์เพิ่มอีกนิดว่า Cache มี 1K line เป็นแบบ 4-way

· จำนวน Set = 1024/4 = 256 set เพราะฉะนั้น set id = 8bit

· word id = 3 bit

· tag id = 20-8-3 = 9 bits

· Ex : address ABCDE = 1010 1011 1100 1101 1110

แบ่งใหม่ตามจำนวน bit = 1 0101 0111 1001 1011 110

นั่นคือ tage = 157

set id = 9B

word offset = 6

5 Line replacement : มี 4 แบบ

5.1. Least recently used (LRU) ให้ copy ทับตัวที่ไม่ได้ถูกใช้งานนานที่สุด

5.2. First in First out : ใช้ queue มาช่วย

5.3. Least frequency used : ให้ copy ทับตัวที่ถูกใช้บ่อยน้อยที่สุด วิธีนี้ต้องมี counter มาช่วยนับ

5.4. Random : แบบนี้ก็แล้วแต่ดวง สุ่ม copy ทับไปเลย

5.5. วิธีที่นิยมใช้กันมากที่สุดคือ LRU (แบบแรก)

6. Write policy : เนื่องจาก cache ไป copy ข้อมูลมาจาก RAM มันจึงต้องมีวิธีทำให้ข้อมูลที่เก็บใน 2 ที่ (RAM กะ Cache) ตรงกัน

6.1. Write through : พอข้อมูลใน cache เปลี่ยนปุ๊ปก็ Update ตัวที่อยู่ใน RAM ทันทีเลย

6.1.1. ข้อดีคือข้อมูล Update ทันที แต่ข้อเสียก็อยู่ที่เสียเวลา Update บ่อยมาก

6.2. Write back : วิธีนี้ถึงแม้ข้อมูลใน cache จะเปลี่ยนไปมันก็จะยังไม่ Update ใน RAM มันจะรอจนกว่าจะถูก swap ออกจาก cache มันจึงจะไป update ใน RAM

· วิธีนี้อาจต้องใช้ bit information มาบอกว่า line ไหนที่เคยถูกเปลี่ยนค่าไปบ้าง เพื่อว่า line ไหน ที่ไม่เคยถูกเปลี่ยนค่า จะได้ไม่ต้องไป update ใน RAM เพื่อประหยัดเวลา เจ้า bit information ที่ว่าก็คือ MESI cache coherency protocol นั่นเอง

7. Block / line size : สรุปว่าไม่มีกฏตายตัวว่าเท่าไหร่ดี ส่วนใหญ่ใช้กันประมาณ 4,8 word / block

8. Number of cache :

8.1. Single vs 2-level : cache L1 จะอยู่ใน CPU เลย ส่วน L2 จะอยู่บน Main board

8.2. Unified vs spilt cache : แบบแรกจะมี 1 cache เก็บทั้ง Instruction และ Data ปนกัน แบบหลังจะแบ่ง cache แยกเก็บ instruction, data แยกจากกัน ซึ่งจะเหมาะกับ CPU ที่ทำงานโดยใช้ pipeline

Integer representation : ก็คือรูปแบบการเก็บตัวเลขจำนวนเต็มด้วย binary bit หรือหมายถึงรูปแบบการนำ binary bit มาเรียงกันอย่างไรให้ทุกคนอ่านแล้วเข้าใจตรงกันว่ามันมีค่าเป็นเท่าไหร่ ซึ่งวิธีเรียงก็มีหลายแบบ

1. Sign magnitude format : วิธีนี้ให้ bit แรกทางซ้ายแสดงถึง +/- ส่วนที่เหลือค่อยตีค่าเป็นตัวเลข

2. Ones complement format : วิธีนี้จะใช้ bit แรกทางซ้ายแสดงถึง +/- เช่นกัน แต่ bit ที่เหลือทางซ้ายแปลกหน่อยตรงที่ว่าถ้าเป็นเลขบวกจะปรกติ แต่ถ้าเป็นเลขลบจะอยู่ในรูป bit ที่ตรงข้ามกับเลขบวก

· +42 = 0 00101010

· -42 = 1 11010101 ให้สังเกตุว่าแต่ละ bit จะตรงข้ามกับเลขบวกของมัน

3. Twos complement format : วิธีนี้จะไม่ใช้ bit แรกมาบอก sign +/- โดยเฉพาะ แต่ถ้าเห็น bit แรกเป็น 1 ก็รู้ได้เลยว่าเป็นเลขลบ (อย่าแปลกใจ มันทำได้แล้วกันน่า) ส่วนเลขบวกก็จะมี bit แรกเป็น 0 แล้วที่เหลือก็ตีค่าธรรมดา พอจะหาค่าลบของมันก็ Invert ทุก bit ให้เป็นตรงข้ามซะ เสร็จแล้วก็บวกเพิ่มอีก 1 ก็จะได้ค่าลบออกมา ซึ่ง bit แรกมันจะกลายเป็น 1 เอง (เห็นไหมว่าไม่ได้ใช้ bit แรกมาเป็น sign +/- โดยเแพาะ แต่เห็นแล้วก็เดาได้ว่าบวกหรือลบ) Rang ตั้งแต่ –128<127

· +42 = 00101010

· -42 = จับ invert ให้หมดแล้วบวกอีก 1 = 11010101 +1 = 11010110

· สรุปอีกทีว่า two complement format ก็คือรูปแบบการแสดงค่าเท่านั้น เช่น

· 0000 1111 มีค่าเท่ากับ 15 , ถ้าbit แรกเป็น 0 ก็อ่านค่าออกมาธรรมดา

· 1000 1111 มีค่าเท่ากับ –113 , ถ้า bit แรกเป็น 1 ถ้าอยากอ่านค่าต้องทำ two complement operation ซะก่อนแล้วค่อยอ่านค่า แต่อย่าลืมใส่ค่าลบไปด้วยเพราะมันเป็นลบอยู่

· two complement operation คือวิธีการกลับค่าเครื่องหมาย เช่นเรามีเลข +42 อยู่แล้วต้องการเลข –42 ก็ทำ two complement operation ซะ โดยการ Invert ทุก bit แล้วบวกเพิ่มอีก 1

Integer addition of n-bit numbers (รายละเอียดดูใน Sheet อีกที แต่คงไม่ออกสอบมั้ง J )

1. การบวก : จะใช้ Ripple adder ต่อ cascade กัน โดยใช้ carry มาช่วยด้วย

2. การลบ : จะเพิ่มวงจรการทำ complement และ Mux เข้าไปในวงจรการบวก (Adder) ก็ทำการลบได้แล้ว

3. การคูณ : ทำได้ 3 วิธี

3.1. Repeated addition : เช่น 6x5 ก็เอา 6 บวกกัน 5 ครั้ง

3.2. Shift and add : วิธีนี้ทำเหมือนกับที่เราทดเลขในกระดาษที่คูณการทีละ bit แล้วออกแบบวงจรให้มีตัว shifter และ Adder ทำงานร่วมกัน

3.3. Hardware speed hardware multipliers : วิธีต้องออกแบบวงจรให้ซับซ้อนมากขึ้น ใช้อุปกรณ์พิเศษมากกว่าแบบ shift and adder เพื่อให้ทำงานแบบขนานและเร็วกว่า อย่างเช่นพวก chip math coprocessor

4. การหาร : ใช้วงจร Shift and adder คล้ายตัวคูณ แต่ออกแบบให้ต่างออกไปหน่อย ก็จะได้วงจรหารแล้ว

Floating point representation

Format = +/-M x R ^+/-E

Mantissas Exponents

Radix

· Mantissa เยอะ เลขจะละเอียดขึ้น

· Exponent เยอะ Rang จะกว้างขึ้น

จบแล้วครับ J / By IT8

ขอขอบคุณ คุณเล็ก...จันทร์เกษม จากใจจริงที่ได้อนุเคราะห์ความรู้และเนื้อหาที่เป็นประโยชน์อย่างสูง