A BUS BASED MULTIPROCESSOR

 Sebuah cara sederhana namun praktis untuk membangun multiprosesor adalah dengan berdasarkan pada sebuah bus di mana lebih dari satu CPU yang terhubung. Jika kita melihat secara dekat Gambar. 6-2 (a), kita melihat bahwa hubungan antara CPU dan memori adalah seperti kumpulan kabel paralel, beberapa memegang alamat CPU yg bisa membaca atau menulis, sebagian untuk mengirim atau menerima data, dan sisanya untuk mengendalikan transfer. Atau sering disebut dengan bus. Bus ini adalah on-chip, tetapi dalam kebanyakan sistem, bus tergolong eksternal dan digunakan untuk menghubungkan mainboard yang mengandung CPU, memori, dan I / O controller. Pada komputer desktop, bus biasanya bergantung pada papan utama (main-board), yang memegang CPU dan beberapa memori, dan ke mana I / O kartu terpasang. Pada minicomputer bus biasanya beroperasi pd rute antara prosesor, memori, dan I / O controller.

Gambar. 6-2 (a) juga menggambarkan suatu sistem dengan tiga CPU dan memori bersama di antara mereka semua. Ketika salah satu CPU ingin membaca sebuah kata dari memori, menempatkan alamat dari kata yang ingin di bus dan menegaskan (menempatkan sinyal pada) jalur bus kontrol mengindikasikan bahwa ia ingin melakukan membaca. Ketika memori telah diambil kata yang diminta, menempatkan kata di bus dan menegaskan garis kontrol lain untuk mengumumkan bahwa ia siap. CPU kemudian membaca dalam kata. Menulis bekerja dengan cara analog.

Untuk mencegah dua atau lebih CPU dari mencoba untuk mengakses memori pada saat yang bersamaan, semacam arbitrase bus diperlukan. Berbagai skema sedang digunakan. Misalnya, untuk mendapatkan bus, CPU pertama mungkin harus meminta dengan menegaskan garis permintaan khusus. Hanya setelah menerima izin baru diperbolehkan untuk menggunakan bus. Pemberian izin ini dapat dilakukan dengan cara yang terpusat, menggunakan perangkat arbitrase bus, atau dengan cara desentralisasi, dengan terlebih dahulu CPU meminta seluruh bus menyelesaikan semua proses.

Kerugian dari memiliki bus tunggal adalah bahwa bus cenderung menjadi kelebihan beban jika dengan sedikitnya digunakan oleh tiga atau empat CPU. Pendekatan yang biasa dilakukan untuk mengurangi beban bus adalah untuk membekali setiap CPU dengan cache penyadap (kadang-kadang disebut cache snoopy), disebut demikian karena "snoops" di dalam bus. Cache ditunjukkan pada Gambar. 6-2 (b). Mereka telah menjadi subyek sejumlah besar penelitian selama bertahun-tahun (Agarwal et al, 1988;. Agarwal dan Cherian, 1989; Archibald dan Baer, ​​1986; Cheong dan Veidenbaum, 1988; Dahlgren et al, 1994;. Eggers dan Katz , 1989a, 1989b, Nayfeh dan Olukotun, 1994; Przybylski et al, 1988;. Scheurich dan Dubois, 1987; Thekkath dan Eggers, 1994; Vernon et al, 1988;. dan Weber dan Gupta, 1989). Semua makalah ini menyajikan protokol konsistensi persediaan yang sedikit berbeda, yaitu, aturan untuk memastikan bahwa cache yang berbeda tidak mengandung nilai yang berbeda untuk lokasi memori yang sama.

Suatu cara yang sangat sederhana dan umum disebut menulis melalui protocol. Ketika CPU pertama membaca sebuah kata dari memori, kata itu diambil melalui bus dan disimpan dalam cache CPU membuat permintaan tersebut. Jika kata tersebut diperlukan lagi nanti, CPU dapat mengambilnya dari cache tanpa membuat permintaan memori, sehingga mengurangi lalu lintas bus. Ada dua kasus, baca miss (kata tidak berada dalam cache) dan membaca hit (kata berada dalam cache) ditunjukkan pada Gambar. 6-3 sebagai dua baris pertama dalam tabel. Dalam sistem yang sederhana, hanya kata yang diminta cache, tetapi lebih seringnya, blok kata-kata, katakanlah, 16 atau 32 kata, yang sudah ditransfer dan cache pada akses awal dan disimpan untuk digunakan di masa depan.

Setiap CPU melakukan caching yang independen dari yang lain. Akibatnya, adalah mungkin untuk kata tertentu untuk di-cache di dua atau lebih CPU pada saat yang sama. Sekarang mari kita perhatikan apa yang terjadi ketika menulis ini dilakukan. Jika tidak ada CPU memiliki kata yang ditulis dalam cache, memori hanya diperbarui, seakan caching tidak sedang digunakan. Operasi ini memerlukan siklus normal bus. Jika CPU melakukan write memiliki satu-satunya salinan kata, cache diperbarui dan memori diperbarui melalui bus juga.

Sejauh ini, begitu baik. Masalahnya muncul ketika CPU ingin menulis sebuah kata yang dua atau lebih CPU memiliki dalam cache mereka. Jika kata tersebut saat ini dalam cache CPU melakukan write, entri cache diperbarui. Apakah itu atau tidak, itu juga tertulis ke bus untuk memperbarui memori. Semua cache lain melihat menulis (karena mereka mengintai di bus) dan memeriksa untuk melihat apakah mereka juga memegang kata yang diubah. Jika demikian, mereka membatalkan entri cache mereka, sehingga setelah selesai menulis, memori up-to-date dan hanya satu mesin memiliki kata dalam cache.

Sebuah alternatif untuk membatalkan entri cache lainnya adalah untuk memperbarui semua dari mereka. Memperbarui lebih lambat dibandingkan membatalkan dalam banyak kasus, namun. Membatalkan membutuhkan memasok hanya alamat yang akan dibatalkan, sedangkan memperbarui kebutuhan untuk menyediakan entri cache yang baru juga. Jika kedua hal ini harus diajukan di bus berurutan, siklus tambahan akan diperlukan. Bahkan jika itu adalah mungkin untuk menempatkan alamat dan kata data pada bus secara bersamaan, jika ukuran blok cache lebih dari satu kata, beberapa siklus bus akan diperlukan untuk memperbarui seluruh blok. Masalah membatalkan vs pembaruan terjadi di semua protokol cache dan juga dalam sistem DSM.

Protokol lengkap diringkas dalam Gambar. 6-3. Kolom pertama berisi empat peristiwa dasar yang bisa terjadi. Yang kedua menceritakan apa cache tidak dalam respon terhadap tindakan CPU sendiri itu. Yang ketiga menceritakan apa yang terjadi ketika cache melihat (dengan mengintip) yang CPU yang berbeda memiliki hit atau miss. Waktu hanya Cache S (pengintai) harus melakukan sesuatu adalah ketika melihat bahwa CPU lain telah menulis sebuah kata yang memiliki cache S (menulis hit dari 5 "s sudut pandang). Tindakan ini untuk S untuk menghapus kata dari cache.

The write-through protokol sederhana untuk memahami dan melaksanakan namun memiliki kelemahan serius bahwa semua menulis menggunakan bus. Sementara protokol tentu mengurangi lalu lintas bus sampai batas tertentu, jumlah CPU yang dapat dilampirkan ke bus tunggal masih terlalu kecil untuk memungkinkan multiprocessors skala besar yang akan dibangun menggunakannya.

Untungnya, bagi banyak program yang sebenarnya, sekali CPU telah menulis sebuah kata, bahwa CPU akan membutuhkan kata lagi, dan tidak mungkin bahwa CPU lain akan menggunakan kata dengan cepat. Situasi ini menunjukkan bahwa jika CPU menggunakan kata entah bagaimana dapat diberikan sementara "kepemilikan" kata, itu bisa menghindari keharusan untuk memperbarui memori pada berikutnya menulis sampai CPU yang berbeda dipamerkan minat dalam kata. Protokol Cache tersebut ada. Goodman (1983) merancang yang pertama, yang disebut menulis sekali. Namun, protokol ini dirancang untuk bekerja dengan bus yang ada dan karena itu lebih rumit dari yang dibutuhkan. Di bawah ini kami akan menjelaskan versi sederhana dari itu, yang khas dari semua protokol kepemilikan. Protokol lain dijelaskan dan dibandingkan oleh Archibald dan Baer (1986).

Protokol kami mengelola blok Cache, yang masing-masing dapat di salah satu dari tiga negara berikut:

1. INVALID - Cache ini blok tidak berisi data yang valid.

2. CLEAN - Memori adalah up-to-date, blok mungkin dalam cache lainnya.

3. DIRTY - Memori tidak benar, tidak ada cache lainnya memegang blok.

Ide dasarnya adalah bahwa sebuah kata yang sedang dibaca oleh beberapa CPU diperbolehkan untuk hadir di semua cache mereka. Sebuah kata yang sedang banyak ditulis oleh hanya satu mesin disimpan dalam cache dan tidak ditulis kembali ke memori pada setiap menulis untuk mengurangi lalu lintas bus.

Operasi protokol terbaik dapat diilustrasikan dengan contoh. Untuk mempermudah dalam contoh ini, kita akan mengasumsikan bahwa setiap blok cache yang terdiri dari satu kata. Awalnya, B memiliki salinan cache dari kata di alamat W, seperti yang diilustrasikan pada Gambar. 6-4 (a). Nilai adalah W1. Memori juga memiliki salinan sah. Dalam Gambar. 6-4 (b), A permintaan dan mendapatkan salinan W dari memori. Meskipun B melihat permintaan membaca berlalu, itu tidak menanggapinya.

Sekarang A menulis nilai baru, W2 ke W. B melihat permintaan menulis dan merespon dengan membatalkan entri cache. A state berubah menjadi DIRTY, seperti ditunjukkan pada Gambar. 6-4 (c). Negara DIRTY berarti bahwa A memiliki satu-satunya salinan cache dari W dan memori yang out-of-date untuk W.

Pada titik ini, A menimpa kata lagi, seperti ditunjukkan pada Gambar. 6-4 (d). Penghapusan dilakukan secara lokal, dalam cache, tanpa lalu lintas bus. Semua selanjutnya menulis juga menghindari memperbarui memori.

Cepat atau lambat, beberapa CPU lainnya, C pada Gambar. 6-4 (e), mengakses kata. A melihat permintaan di bus dan menegaskan sinyal yang menghambat memori dari menanggapi. Sebaliknya, A memberikan kata dibutuhkan dan membatalkan entri sendiri. C melihat bahwa kata tersebut berasal dari cache yang lain, bukan dari memori, dan bahwa itu adalah dalam keadaan DIRTY, sehingga menandai masuknya yang sesuai. C kini pemilik, yang berarti bahwa sekarang dapat membaca dan menulis kata tanpa membuat permintaan bus. Namun, juga memiliki tanggung jawab untuk mengawasi keluar untuk CPU lain yang meminta kata, dan melayani mereka sendiri. Kata tetap dalam keadaan DIRTY sampai itu CLEAN dari cache itu saat ini berada di karena kurangnya ruang. Pada waktu itu menghilang dari semua cache dan ditulis kembali ke memori.

Banyak multiprocessors kecil menggunakan konsistensi persediaan protokol yang sama dengan yang satu ini, sering dengan variasi kecil. Ia memiliki tiga sifat penting:

1. Konsistensi dicapai dengan memiliki semua cache melakukan mengintai bus.

2. Protokol ini dibangun ke dalam unit manajemen memori.

3. Seluruh Algoritma dilakukan baik di bawah siklus memori.

Seperti yang akan kita lihat nanti, beberapa tidak tahan untuk lebih besar (switched) multiprocessors, dan tidak satupun dari mereka pegang untuk memori bersama didistribusikan.

😊