Perangkat Keras untuk Aritmetika, CPU • Topik Hari ini: Mendesain sebuah ALU Penambah Carry-lookahead Jam dan sirkuit sequential Mesin finite state CPU siklus tunggal CPU siklus ganda
1
Hukum DeMorgan’s • A+B=A.B
• A.B = A+B
•Konfirmasikan bahwa yang diatas benar
2
Jumlah dari Perkalian •Dapat melambangkan semua blok logika dengan operator AND, OR, NOT Menggambar tabel kebenaran Untuk setiap output yang true, gambarkan input-inputnya sebagai hasil perkalian Persamaan akhir adalah jumlah dari perkalian – perkalian ini
A
B
C
E
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0 0 0 1 0 1 1 0
(A . B . C) + (A . C . B) + (C . B . A) •Dapat juga menggunakan “perkalian dari penjumlahan” •Semua persamaan dapat dinyatakan dengan sebuah array dari AND, diikuti dengan sebuah array dari OR 3
Algoritma Penjumlah
Sum Carry
1 0 1 0
0 1 1 0
0 0 1 0
1 1 0 1
Tabel kebenaran dari operasi ini:
A
B
Cin
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
Sum Cout 0 1 1 0 1 0 0 1
0 0 0 1 0 1 1 1
Persamaan: Sum = Cin . A . B + B . Cin . A + A . Cin . B + A . B . Cin Cout = A . B . Cin + A . B . Cin + A . Cin . B + B . Cin . A =A.B + A . Cin + B . Cin 4
Carry Out Logic Persamaan: Sum = Cin . A . B + B . Cin . A + A . Cin . B + A . B . Cin Cout = A . B . Cin + A . B . Cin + A . Cin . B + B . Cin . A =A.B + A . Cin + B . Cin
5
1-Bit ALU dengan Add, Or, And •Multiplekso memilih antara operasi Add, Or, And
6
32-bit Penjumlah Ripple Carry
1-bit ALUs dihubungkan secara seri dengan carryout dari 1 boks disambung kan dengan carry-in dari boks berikutnya
7
Melakukan Pengurangan
Harus membalikkan bit – bit dari B dan menambahkan 1 •Memasukkan inverter •Carry-in untuk bit pertama: 1 •Signal Carry-ini (untuk bit pertama) dapat disamakan dengan signal Binvert
8
Menjalankan NOR
9
Menjalankan slt •Lakukan a – b dan cek tandanya •Signal baru (Less) adalah nol untuk boks boks ALU 1 - 31 •Boks ke 31 punya sebuah unit utk mengecek overflow dan tanda - . Bit tanda berperan sebagai signal Less untuk boks ke 0
10
Menjalankan beq •Lakukan a – b dan konfirmasi bahwa hasilnya semuanya nol
11
Baris – baris Kontrol Berapakah nilai – nilai dari baris – baris kontrol dan operasi apakah yang sedang dilakukan?
12
Baris – baris Kontrol Berapakah nilai – nilai dari baris – baris kontrol dan operasi apakah yang sedang dilakukan?
AND OR Add Sub SLT NOR
Ai Bn Op 0 0 00 0 0 01 0 0 10 0 1 10 0 1 11 1 1 00
13
Kecepatan dari Ripple Carry •Carry merambat melalui setiap boks: setiap boks 1-bit secara berurutan mengimplementasikan AND dan OR – delay total adalah waktu yang diperlukan untuk menempuh 64 gate! •Kita telah melihat bawah semua persamaan logic dapat dinyatakan sebagai penjumlahand dari perkalian – jadi memungkinkan untuk menghitung hasil dengan melalui hanya 2 gate!
•Perhatian: membutuhkan banyak gate – gate paralel dan mungkin memiliki banyak input – sangat sulit membangun gate yang sangat besar ini, jadi butuh kompromi: Jumlah gate yang moderat Jumlah input yang moderat setiap gate-nya Jumlah rambatan sekuensial pada gate yang moderat 14
Menghitung CarryOut CarryIn1 = b0.CarryIn0 + a0.CarryIn0 + a0.b0 CarryIn2 = b1.CarryIn1 + a1.CarryIn1 + a1.b1 = b1.b0.c0 + b1.a0.c0 + b1.a0.b0 + a1.b0.c0 + a1.a0.c0 + a1.a0.b0 + a1.b1 … CarryIn32 = sebuah nilai yang sangat besar dari sebuah perkalian besar •Implementasi potensial yang cepat sebagai hasil yang dihitung dengan hanya melewati 2 tingkat dari logic – sayangnya setiap gate menjadi sangat besar dan lambat 15
Generate dan Propagate Persamaan ditataulang: Ci+1 = ai.bi + ai.Ci + bi.Ci = (ai.bi) + (ai + bi).Ci Secara verbal, pasangan bit yang terkini akan menghasilkan (generate) sebuah carry apabila keduanya 1 dan pasangan bit yang terkini akan meneruskan (propagate) jika sebuah carry jika salah satunya 1 Generate signal = ai.bi Propagate signal = ai + bi Maka, Ci+1 = Gi + Pi . Ci
16
Generate dan Propagate c1 = g0 + p0.c0 c2 = g1 + p1.c1 = g1 + p1.g0 + p1.p0.c0 c3 = g2 + p2.g1 + p2.p1.g0 + p2.p1.p0.c0 c4 = g3 + p3.g2 + p3.p2.g1 + p3.p2.p1.g0 + p3.p2.p1.p0.c0
Salah satu, sebuah carry telah dibuat, atau sebuah carry telah dibuat dari langkah sebelumnya dan dirambatkan, atau sebuah carry telah dibuat dua langkah sebelumnya dan dirambatkan oleh dua tahap selanjutnya, atau sebuah carry telah dibuat N langkah sebelumnya dan dirambatkan oleh setiap buah dari N tahap selanjutnya 17
Membagi dan Menguasai •Persamaan dari slide sebelumnya masih sulit untuk diimplementasikan sebagai sebuah fungsi logic – untuk bit ke 32, kita harus AND setiap bit rambatan untuk menetukan apa yang menjadi c0 (juga hasil lainnya) •Maka, bit – bit dipecah menjadi grup (ber-empat) dan setiap grup menghitung grup-generate dan grup-propagate •Sebagai contoh, untuk menambah 32 angka, kita bisa membagi tugas dalam sebuah pohon
. . . . . .... .... .... .... 18
P dan G untuk 4-bit Blocks •Menghitung P0 dan G0 (super-propagate dan super-generate) untuk grup pertama dari 4 bit (dan sama halnya untuk grup 4 bit lainnya) P0 = p0.p1.p2.p3 G0 = g3 + g2.p3 + g1.p2.p3 + g0.p1.p2.p3 •Carry out dari grup pertama 4 bit adalah C1 = G0 + P0.c0 C2 = G1 + P1.G0 + P1.P0.c0 … •Dengan menggunakan sebuah pohon sub-komputasi, setiap gate AND, OR memiliki input yang sediki dan signal logic harus menempuh serangkaian gate yang sedikit (sama dengan tinggi dari pohon).
19
Contoh Add A 0001 and B 1110 g 0000 p 1111 P G
1 0
1010 0101 0000 1111 1 0
0011 1110 0010 1111 1 1
0011 1011 0011 1011 0 0
C4 = 1
20
Penjumlah Carry Look-Ahead • 16-bit Ripple-carry membutuhkan 32 langkah •Desain ini butuh berapa langkah?
21
Clock •Sebuah mikroprosesor terdiri dari banyak sirkuit yang berbeda yang berjalan bersamaan – jika setiap sirkuit X membutuhkan input saat TIX, membutuhkan waktu TEX untuk mengeksekusi, and menghasilkan output saat TOX, bayangkan komplikasi dalam mengkoordinasi tugas – tugas setiap sirkuit •Sebuah pemikiran utama (digunakan dalam hampir semua prosesor sekarang): semua sirkuit dalam chip share sebuah signal clock (sebuah gelombang kotak) yang memberitahu setiap sirkuit kapan menerima input, waktu yang digunakan untuk mengeksekusi, dan kapan mengeluarkan output 22
Terminologi Clock
Rising clock edge Waktu siklus
Falling clock edge
4 GHz = clock speed =
1 waktu siklus
=
1 . 250 ps 23
Sirkuit Sekuensial •Sampai sekarang, sirkuit adalah kombinasional – ketika input berubah, outputnya akan berubah kemudian (waktu = delay logic melewati sirkuit Inputs
Combinational Circuit
Outputs
Combinational Circuit
•Kita ingin clock berperan sebagai sebuah signal start dan stop – sebuah “latch” adalah sebuah alat penyimpanan yang menyimpan inputnya saat rising clock edge dan nilainya tidak berubah sampai rising clock edge berikutnya Clock Clock Combinational Outputs Circuit
Inputs Latch
Combinational Circuit Latch
24
Sirkuit Sekuensial •Sirkuit sekuensial: terdiri dari kombinasi sirkuit kombinasional Inputs dan elemen penyimpan Clock •Saat awal siklus clock, rising Inputs edge membuat kondisi penyimpanan menyimpan beberapa nilai input
State Outputs Combinational Cct
•Kondisi ini tidak berubah sepanjang siklus (sampai rising edge berikutnya •Sirkuit kombinasional memiliki beberapa saat untuk menerima nilai dari kondisi dan inputnya serta menghasilkan output •Beberapa outputnya (contoh, nilai dari kondisi selanjutnya) mungkin diumpanbalikkan (meski lewat latch sehingga diketahui saat siklus berikut 25 nya
Mendesain sebuah Latch •Sebuah S-R latch: set-reset latch •An S-R latch: set-reset latch Ketika Set tinggi, sebuah 1 disimpan Ketika Reset tinggi, sebuah 0 disimpan Ketika keduanya rendah, kondisi sebelumnya dipertahankan (maka disebut penyimpan atau elemen memori) Ketika keduanya tinggi, outputnya tidak stabil – kondisi input ini tidak diijinkan Verifikasi perilaku diatas!
26
D Latch •Memasukkan sebuah clock •Nilai dari signal D input (data) disimpan jika clock tinggi – kondisi sebelum nya dipertahankan bila clock rendah
27
D Flip Flop •Terminologi: Latch: output dapat berubah setiap clock yang tinggi Flip flop: output dapat berubah hanya saat clock edge •Dua D latch disusun seri – memastikan bahwa sebuah nilai disimpan hanya saat falling edge dari clock
28
Sirkuit Sekuensial •Kita ingin clock berperan sebagai sebuah signal start dan stop – sebuah “latch adalah sebuah alat penyimpan yang menyimpan inputnya saat rising edge dari clock dan penyimpanan ini tidak berubah sampai rising edge berikutnya dari clock Clock
Clock Combinational Outputs Circuit
Inputs Latch
Combinational Circuit Latch
29
Mesin Finite State •Sebuah sirkuit sekuensial digambarkan sebuah sebuah variasi dari tabel kebenaran – sebuah diagram finite state (maka, sirkuit ini juga disebut sebuah mesin finite state) •Catatan: state atau kondisi hanya diperbaharui pada clock edge
Clock
Inputs
Current State
Next-state Function
Output Function
Next state
Outputs
30
State Diagram •Setiap state digambarkan sebagai sebuah lingkaran, dilabel dengan nilai state-nya – isi dari lingkaran adalah outputnya •Anak panah menunjukkan sebuah transisi ke state yang lainnya, dengan input diindikasikan pada labelnya
D=0
D=1 Ini adalah state diagram untuk?
D=1
0
0
1
1
D=0 31
Pencacah 3-Bit •Pertimbangkan sebuah sirkuit yang menyimpan sebuah angka dan menaikkan nilainya setiap clock edge – saat mencapai nilai tertinggi, nilainya kembali ke 0 Gambarkan state diagram: Berapa jumlah state-nya? Berapa jumlah inputnya?
32
Pencacah 3-Bit •Pertimbangkan sebuah sirkuit yang menyimpan sebuah angka dan menaikkan nilainya setiap clock edge – saat mencapai nilai tertinggi, nilainya kembali ke 0 Gambarkan state diagram: Berapa jumlah state-nya? Berapa jumlah inputnya?
000
001
010
011
100
101
110
111
000
001
010
011
100
101
110
111 33
Pengatur Lampu Lalu Lintas •Penjelasan masalah: sebuah lampu lalu lintas (hanya merah dan hijau); hanya salah satu dari Utara – Selatan atau Timur – Barat hanya boleh hijau (kedua arah tidak boleh merah bersamaan); terdapat detektor di jalan untuk mendeteksi adanya mobil di jalan; lampu diperbaharui setiap 30 detik; sebuah lampu hanya berubah jika terdapat sebuah mobil yang menunggu di jalan lawannya. Tabel transisi state: Berapa jumlah state-nya? Berapa jumlah inputnya? Berapa jumlah outputnya?
34
Tabel Transisi State Penjelasan masalah: sebuah lampu lalu lintas (hanya merah dan hijau); hanya salah satu dari Utara – Selatan atau Timur – Barat hanya boleh hijau (kedua arah tidak boleh merah bersamaan); terdapat detektor di jalan untuk mendeteksi adanya mobil di jalan; lampu diperbaharui setiap 30 detik; sebuah lampu hanya berubah jika terdapat sebuah mobil yang menunggu di jalan lawannya.
Tabel transisi state: CurrState InputEW N 0 N 0 N 1 N 1 E 0 E 0 E 1 E 1
InputNS 0 1 0 1 0 1 0 1
NextState=Output N N E E E N E N
35
State Diagram Tabel transisi state: CurrState InputEW N 0 N 0 N 1 N 1 E 0 E 0 E 1 E 1
InputNS 0 1 0 1 0 1 0 1
NextState=Output N N E E E N E N
36
Arsitektur Dasar MIPS •Sekarang kita memahami clock dan penyimpan (storage) dari state, kita akan mendesain CPU sederhana yang mengeksekusi: Matematika dasar (add, sub, and, or, slt) Akses memori (lw dan sw) Instruksi branch dan jump (beq dan j)
37
Overview dari Implementasi •Kita butuh memori Untuk menyimpan instruksi Untuk menyimpan data Sekarang ini, keduanya dianggap unit yang berbeda •Kita butuh register – register, ALU, dan banyak kontrol logic •Operasi CPU yang sama untuk setiap instruksi: Menggunakan program counter (PC) untuk menarik instruksi dari memori instruksi Membaca nilai register 38
Pandangan dari 30,000 Kaki
Catatan: Kita belum menunjukkan multipleksornya
•Apakah peran dari unit Add? •Jelaskan input dari unit memori data •Jelaskan input dari ALU •Jelaskan input dari unit register
39
Metodologi Clocking
•Dimanakan diantara unit – unit ini yang membutuhkan clock? •Apakah yang akan disimpan (latched) pada rising edge dari clock? •Pertimbangkan bahwa nilai yang di-latch akan ada untuk sepanjang 40 siklus
Implementasi Instruksi Tipe R •Instruksi dalam bentuk add $t1, $t2, $t3 •Jelaskan peran dari masing – masing signal
41
Implementasi dari Loads/Stores • Instruksi dalam bentuk lw $t1, 8($t2) dan sw $t1, 8($t2)
Dimanakan input ini berasal? 42
Implementasi Instruksi Tipe J •Instruksi dalam bentuk beq $t1, $t2, offset
43
Pandangan dari 10,000 Kaki
44
Pandangan dari 5,000 Kaki
45
Mesin Siklus Tunggal Vs. Ganda •Pada implementasi ini, setiap instruksi membutuhkan satu siklus untuk selesai waktu siklus = waktu yang dibutuhkan untuk siklus terlama •Jika eksekusi dipecah menjadi siklus banyak (lebih cepat), instruksi yang lebih pendek akan selesai lebih dulu Waktu siklus = 20 ns Load Add Beq
1 cycle 1 cycle 1 cycle
Waktu untuk load, add, dan beq = 60 ns
Waktu siklus = 5 ns Load Add Beq
4 cycles 3 cycles 2 cycles 45 ns
46
Prosesor Siklus Ganda
•Unit memori tunggal di-share oleh instruksi dan memori •ALU tunggal juga dipergunakan untuk update PC •Register (latches) untuk menyimpan hasil dari setiap blok 47
Siklus 1 •PC dipergunakan untuk memilih instruksi yang sesuai untuk dikeluarkan dari unit memori •Instruksi di-latch ke register instruksi di akhir clock cycle •ALU menjalankan PC+4 dan menyimpannya di dalam PC pada akhir clock cycle (catatan bahwa ALU bebas di siklus ini) •Sirkuit kontrol sekarang harus “cycle-aware” – PC yang baru tidak perlu melihat instr-memori sampai kita selesai dengan instruksiyang sekarang 48
Siklus 2 •Instruksi menspesifikasi nilai register yang diminta – ini adalah pembacaan dari berkas register dan menyimpannya dalam latch A dan B (ini terjadi meskipun operands tidak dibutuhkan) •16 bit terakhir dipergunakan untuk menghitung PC+4+offset (jika instruksi ini ternyata sebuah brach) – ini di-latch menjadi ALUOut •Catatan bahwa kita belum menentukan tipe instruksinya, maka operasi diatas adalah “spekulatif” 49
Siklus 3 Operasinya tergantung dari tipe instruksi •Akses memori: alamat dihitung dengan menambahkan offset pada nilai yang dibaca pada berkas register, hasilnya di-latch dalam ALUOut. •ALU: Operasi ALU dilaksanakan pada nilai yang terbaca dari berkas register dan hasilnya di-latch dalam ALUOut •Branch: ALU melaksanakan operasi untuk “beq” dan jika terjadi branch, target branch-nya (saat ini ada di ALUOut) di-latch ke PC di akhir siklus •Catatan bahwa operasi branch berakhir pada akhir siklus 3, operasi yang lain masih berlanjut
50
Siklus 4 •Akses memori: alamat dalam ALUOut digunakan untuk mengambil sebuah word dalam memori – ini di-latch ke dalam register data memori •ALU: hasil di-latch dalam ALUOut diumpankan sebagai input pada berkas register, instruksi yang tersimpan dalam latch-instruksi menspesifikasi dimana hasilnya harus dituliskan •Di akhir siklus, operasi ALU dan penulisan memori telah selesai 51
Siklus 5 •Pembacaan memori: nilai yang dibaca dari memori (dan di-latch ke dalam register data memori) sekarang ditulis ke dalam berkas register • Ringkasan: Branch dan jump: 3 siklus ALU, store: 4 siklus Akses memori: 5 siklus ALU lebih lambat karena membutuhkan penulisan ke berkas register Store lebih lambat karena membutuhkan penulisan ke data memori Load lebih lambat kerena membutuhkan pembacaan data 52 memori dan penulisan ke berkas register
Rata - rata CPI •Sekarang kita bisa menghitung CPI rata – rata dari sebuah program: jika sebuah program terdiri dari load (25%), store (10%), branch (13%), dan operasi ALU (52%), rata – rata CPI adalah 0.25 x 5 + 0.1 x 4 + 0.13 x 3 + 0.52 x 4 = 4.12 •Anda dapat memecah desain CPU ini menjadi siklus yang lebih pendek, contohnya, sebuah load membutuhkan 10 siklus, store 8, ALU 8, branch 6 rata – rata CPI akan dobel, tapi juga kecepatan clocknya, kinerja netnya akan kira – kira sama. •Selanjutnya, kita akan melihat apakah strategi ini akan membantu dalam kasus – kasus yang lainnya 53
Kontrol Logic •Tercatat bahwa signal – signal kontrol untuk setiap unit akan ditentukan oleh 2 faktor: Tipe instruksi Jumlah siklus dari instruksi ini Maka, kontrolnya diimplementasikan sebagai sebuah mesin finite state – setiap siklus, transisi FSM ke state yang baru dengan set output tertentu (signal – signal kontrol) dan ini adalah fungsi dari inputnya (tipe instr).
54
