Desain Rangkaian Aritmatika: Fast Adder Eko Didik Widianto (
[email protected]) Sistem Komputer - Universitas Diponegoro
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 1 / 18
Review Kuliah • Di kuliah sebelumnya dibahas tentang operasi penjumlahan dan pengurangan bilangan biner serta unit penjumlah/pengurang dan susunan rangkaian penjumlah ripple-carry (RCA) • Rangkaian RCA mempunyai kekurangan terkait delay yang ditimbulkan. Selanjutnya akan dibahas tentang rangkaian aritmatika berupa fast adder sebagai pengganti RCA
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 2 / 18
Bahasan Performansi Rangkaian Isu Performansi Performansi Adder/Subtractor Carry-lookahead Adder (CLA) Carry-lookahead Adder Critical Path CLA Keterbatasan CLA Desain Adder Adder 32-bit Ripple-Carry Antar Blok Carry-lookahead Level-2 Analisis Rangkaian CLA Hirarki
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 3 / 18
Performansi Rangkaian
• Isu Performansi • Performansi Adder/Subtractor Carry-lookahead Adder (CLA) Desain Adder
Performansi Rangkaian
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 4 / 18
Isu Performansi Performansi Rangkaian
• Isu Performansi • Performansi Adder/Subtractor Carry-lookahead Adder (CLA)
• Penjumlahan dan pengurangan merupakan operasi dasar di sistem komputer sebagai perangkat komputasi
◦
Performansi operasi ini (mis: kecepatan) membawa pengaruh signifikan terhadap performansi keseluruhan
◦
Meningkatkan performansi dapat menggunakan rangkaian yang lebih cepat
Desain Adder
• Menggunakan teknologi terbaru yang mengurangi delay gerbang dasar
◦
Performansi bisa diperoleh dengan mengubah struktur rangkaian fungsional
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 5 / 18
Performansi Adder/Subtractor Performansi Rangkaian
• Isu Performansi • Performansi Adder/Subtractor Carry-lookahead Adder (CLA)
• Identifikasi jalur yang menyebabkan delay terbesar (critical path) • Recall critical path di RCA:
Desain Adder
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 6 / 18
Performansi Rangkaian Carry-lookahead Adder (CLA)
• Carry-lookahead Adder • Critical Path CLA • Keterbatasan CLA Desain Adder
Carry-lookahead Adder (CLA)
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 7 / 18
Carry-lookahead Adder Performansi Rangkaian Carry-lookahead Adder (CLA)
•
Untuk mengurangi delay akibat propagasi carry di RCA (critical-path-delay)
• Carry-lookahead Adder • Critical Path CLA • Keterbatasan CLA
◦
Evaluasi tiap stage FA apakah carry-in dari stage sebelumnya akan mempunyai nilai 0 atau 1
Desain Adder
◦
Jika evaluasi dapat dilakukan dengan cepat, performasi adder dapat ditingkatkan
•
Recall FA yang ada di tiap stage:
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 8 / 18
Carry-lookahead Adder Performansi Rangkaian Carry-lookahead Adder (CLA)
• Carry-lookahead Adder • Critical Path CLA • Keterbatasan CLA
• Fungsi carry-out dari stage i (satu FA) adalah
ci+1 = xi yi + xi ci + yi ci = xi yi + (xi + yi ) ci • Anggap gi = xi yi dan pi = xi + yi , maka ci+1 = gi + pi ci
Desain Adder
◦ Fungsi gi = 1 jika xi = 1 dan yi = 1, tanpa pengaruh ci . Stage i pasti membangkitkan carry-out, sehingga g disebut fungsi generate ◦ Fungsi pi = 1 jika salah satu xi = 1 atau yi = 1 atau keduanya 1. Stage i membangkitkan carry-out jika ci = 1. Nilai ci = 1 ini dipropagasikan lewat FA di stage i, sehingga p disebut fungsi propagate
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 9 / 18
Carry-lookahead Adder Performansi Rangkaian Carry-lookahead Adder (CLA)
• Carry-lookahead Adder • Critical Path CLA • Keterbatasan CLA
• Ekspansi persamaan ci+1 = gi + pi ci . Dengan ci = gi−1 + pi−1 ci−1 , akan menghasilkan
ci+1
Desain Adder
= gi + pi (gi−1 + pi−1 ci−1 ) = gi + pi gi−1 + pi pi−1 ci−1
• Ekspansi sampai stage 0:
ci+1
= gi + pi gi−1 + pi pi−1 gi−2 + · · · + pi pi−1 · · · p2 p1 g0 +pi pi−1 · · · p2 p1 p0 ci−1
• Ekspresi tersebut menggambarkan rangkaian AND-OR 2-level yang memungkinkan ci+1 dapat dihasilkan dengan cepat ◦ Ini disebut carry-lookahead adder @2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 10 / 18
Critical Path CLA Performansi Rangkaian Carry-lookahead Adder (CLA)
• Carry-lookahead Adder • Critical Path CLA • Keterbatasan CLA Desain Adder
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 11 / 18
Keterbatasan CLA Performansi Rangkaian Carry-lookahead Adder (CLA)
• Carry-lookahead Adder • Critical Path CLA • Keterbatasan CLA
• Persamaan carry-out di CLA menghasilkan solusi adder yang cepat karena hanya merupakan fungsi AND-OR 2-level • Namun, batasan fan-in dapat membatasi kecepatan CLA
Desain Adder
◦ ◦ ◦ ◦
FA0 : AND dan OR 2-input, c1 = g0 + p0 c0 FA1 : AND dan OR 3-input, c2 = g1 + p1 g0 + p1 p0 c0 FA2 : AND dan OR 4-input, c3 = g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 c0 FAn : AND dan OR (n+2)-input
• Device seperti FPGA seringkali menggunakan rangkaian khusus untuk implementasi fast adder • Kompleksitas CLA n-bit akan bertambah jika n bertambah ◦ Untuk menguranginya, digunakan pendekatan hirarki untuk mendesain adder yang lebih besar
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 12 / 18
Performansi Rangkaian Carry-lookahead Adder (CLA) Desain Adder
• Adder 32-bit • Ripple-Carry Antar Blok • Carry-lookahead Level-2 • Analisis Rangkaian CLA Hirarki
Desain Adder
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 13 / 18
Adder 32-bit Performansi Rangkaian Carry-lookahead Adder (CLA) Desain Adder
• Adder 32-bit • Ripple-Carry Antar Blok • Carry-lookahead Level-2 • Analisis Rangkaian CLA Hirarki
• Misalnya diinginkan rangkaian penjumlah 32-bit • Bagi adder ini menjadi 4 blok sehingga ◦ Blok 0 untuk operasi bit b7 − b0 ◦ Blok 1 untuk operasi bit b15 − b8 ◦ Blok 2 untuk operasi bit b23 − b16 ◦ Blok 3 untuk operasi bit b31 − b24 • Tiap blok dibangun dengan adder CLA 8-bit ◦ Carry-out untuk tiap blok adalah c8 , c16 , c24 dan c32 • Terdapat 2 pendekatan untuk menghubungkan ke-empat blok ◦ Ripple-carry ◦ Carry-lookahead level-2
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 14 / 18
Ripple-Carry Antar Blok Performansi Rangkaian Carry-lookahead Adder (CLA) Desain Adder
• Adder 32-bit • Ripple-Carry Antar Blok • Carry-lookahead Level-2 • Analisis Rangkaian CLA Hirarki
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 15 / 18
Carry-lookahead Level-2 Performansi Rangkaian Carry-lookahead Adder (CLA) Desain Adder
• Adder 32-bit • Ripple-Carry Antar Blok • Carry-lookahead Level-2 • Analisis Rangkaian CLA Hirarki
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 16 / 18
Carry-lookahead Level-2 Performansi Rangkaian Carry-lookahead Adder (CLA) Desain Adder
• Adder 32-bit • Ripple-Carry Antar Blok • Carry-lookahead Level-2 • Analisis Rangkaian CLA Hirarki
• Persamaan CLA level-2
P0 = p7 p6 p5 p4 p3 p2 p1 p0 G0 = g7 + p7 g6 + p7 p6 g5 + · · · + p7 p6 p5 p4 p3 p2 p1 g0 c8 = G 0 + P 0 c0 c16 = G1 + P1 c8 = G1 + P1 G0 + P1 P0 c0 c24 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 c0 c32 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 c0
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 17 / 18
Analisis Rangkaian CLA Hirarki Performansi Rangkaian Carry-lookahead Adder (CLA)
• Asumsi konstrain fan-in adalah 4 masukan, waktu yang diperlukan untuk melakukan operasi penambahan 2 bilangan 32-bit meliputi:
Desain Adder
• Adder 32-bit • Ripple-Carry Antar Blok • Carry-lookahead Level-2 • Analisis Rangkaian CLA Hirarki
◦ Lima delay gerbang untuk membentuk term Gi dan Pi , 3 delay gerbang untuk CLA level-2, dan satu delay untuk menghasilkan bit sum akhir •
Sebenarnya bit sum final diperoleh setelah 8 delay karena c32 tidak digunakan untuk menghitung bit sum
◦ Operasi lengkap, termasuk deteksi overflow (c31 ⊕ c32 ), membutuhkan 9 delay gerbang •
Bandingkan 65 delay di ripple-carry adder
@2011 eko didik widianto (http://didik.blog.undip.ac.id)
TSK205 Sistem Digital - Siskom Undip – 18 / 18
