Penjadwalan Thread untuk Multiprosesor Multiprogram

Nimar S. Arora Robert D. Blumofe C. Greg Plaxton
Departemen Ilmu Komputer, Universitas Texas di Austin{nimar,rdb,plaxton}@cs.utexas.edu

Abstrak

Kami menyajikan penjadwal utas tingkat pengguna untuk multiprosesor memori bersama, dan kami menganalisis kinerjanya di bawah multiprogramming. Kami memodelkan multiprogramming dengan dua tingkat penjadwalan: penjadwal kami berjalan di tingkat pengguna dan menjadwalkan utas ke kumpulan proses tetap, sedangkan di bawahnya, kernel sistem operasi menjadwalkan proses ke kumpulan prosesor tetap. Kami menganggap kernel sebagai musuh, dan tujuan kami adalah untuk menjadwalkan utas ke proses sedemikian rupa sehingga kami menggunakan sumber daya prosesor apa pun yang disediakan oleh kernel secara efisien. Penjadwal utas kami adalah implementasi non-pemblokiran dari algoritma pencurian pekerjaan. Untuk komputasi multithreaded apa pun dengan panjang kerja $T_{1}$ dan jalur kritis $T_{\infty}$ , dan untuk sejumlah $P$ proses, penjadwal kami mengeksekusi komputasi dalam waktu yang $O (T_{1} / P_{A} + T_{\infty} P / P_{A})$ diharapkan , di mana $P_{A}$ adalah jumlah rata-rata prosesor yang dialokasikan untuk komputasi oleh kernel. Batas waktu ini optimal dalam faktor konstan, dan mencapai percepatan linier setiap kali $P$ relatif kecil terhadap paralelisme $T_{1} / T_{\infty}$ rata-rata.

1 Pengantar

Untuk multiprosesor memori bersama, aplikasi paralel menggunakan beberapa utas dan dikodekan menggunakan kompiler paralel, pustaka utas, atau bahasa multiutas seperti Cilk [7,18] atau Java [3]. Selain mendukung aplikasi multithreaded, multiprosesor juga mendukung beban kerja multiprogram di mana campuran aplikasi serial dan paralel, interaktif, dan batch dapat dijalankan secara bersamaan. Faktor utama dalam performa beban kerja tersebut adalah pengoperasian penjadwal utas.

Pekerjaan sebelumnya pada penjadwalan utas [4, 5, 8, 11, 12] telah berurusan secara eksklusif dengan lingkungan non-multiprogram di mana komputasi multithreaded dieksekusi pada

P

prosesor khusus. Algoritme penjadwalan tersebut secara dinamis memetakan utas ke prosesor dengan tujuan mencapai

P

percepatan -fold. Meskipun algoritma semacam itu akan bekerja di beberapa lingkungan multiprogram, khususnya yang menggunakan partisi ruang statis [13, 26] atau coscheduling

{15, 26, 29]

, mereka tidak bekerja di lingkungan multiprogram yang didukung oleh multiprosesor dan sistem

[9, 13, 14, 20]

operasi memori bersama modern. Masalahnya

terletak pada asumsi bahwa kumpulan prosesor tetap sepenuhnya tersedia untuk melakukan perhitungan tertentu.

Dalam lingkungan multiprogram, komputasi paralel berjalan pada kumpulan prosesor yang tumbuh dan menyusut dari waktu ke waktu. Awalnya komputasi mungkin satu-satunya yang berjalan, dan mungkin menggunakan semua

P

prosesor. Sesaat kemudian, seseorang mungkin meluncurkan komputasi lain, mungkin komputasi serial, yang berjalan pada beberapa prosesor. Dalam hal ini, komputasi paralel melepaskan satu prosesor dan terus berjalan pada prosesor yang tersisa

P - 1

. Kemudian, jika komputasi serial dihentikan atau menunggu I/O, komputasi paralel dapat melanjutkan penggunaan semua prosesor. Secara umum, komputasi serial dan paralel lainnya dapat menggunakan prosesor dengan cara yang bervariasi waktu yang berada di luar kendali kami. Dengan demikian, kami berasumsi bahwa musuh mengontrol kumpulan prosesor tempat komputasi paralel berjalan.

Secara khusus, alih-alih memetakan utas ke prosesor, penjadwal utas kami memetakan utas ke kumpulan

P

proses tetap, dan musuh memetakan proses ke prosesor. Dengan demikian, kami memodelkan lingkungan multiprogram dengan dua tingkat penjadwalan. Penjadwal tingkat pengguna - penjadwal kami - memetakan utas ke proses, dan di bawah tingkat ini, kernel - musuh - memetakan proses ke prosesor. Dalam lingkungan ini, kita tidak dapat berharap untuk mencapai

P

percepatan -fold, karena kernel dapat menjalankan komputasi kita pada lebih sedikit dari

P

prosesor. Sebaliknya, kita biarkan menunjukkan

P_{A}

jumlah rata-rata waktu prosesor di mana kernel mengeksekusi komputasi kita, dan kita berusaha untuk mencapai percepatan -

P_{A}

fold.

Seperti banyak pekerjaan sebelumnya, kami memodelkan komputasi multithreaded sebagai grafik asiklik terarah, atau dag. Setiap simpul dalam dag mewakili satu instruksi, dan tepi mewakili batasan pemesanan. Node thread dihubungkan oleh tepi yang membentuk rantai yang sesuai dengan urutan eksekusi instruksi dinamis thread. Selain itu, ketika instruksi dalam satu utas memunculkan utas baru, maka dag memiliki tepi dari simpul "pemijahan" di utas pertama ke simpul pertama di utas baru. Demikian juga, setiap kali utas menyinkronkan sedemikian rupa sehingga instruksi dalam satu utas tidak dapat dikeluarkan sampai setelah beberapa instruksi di utas lain, maka dag berisi tepi dari simpul yang mewakili instruksi terakhir ke simpul yang mewakili instruksi sebelumnya. Pekerjaan

T_{1}

perhitungan adalah jumlah simpul dalam dag, dan panjang

T_{\infty}

jalur kritis adalah panjang jalur terpanjang (terarah) di dag. Rasio

T_{1} / T_{\infty}

ini disebut paralelisme rata-rata. Dag dihasilkan secara dinamis selama eksekusi, dan penjadwal beroperasi secara on-line. Ketika semua induk dari sebuah node dieksekusi, kita mengatakan bahwa node sudah siap, dan hanya node siap yang dapat dieksekusi.

Kami membuat dua asumsi terkait dengan struktur dag. Pertama, kita berasumsi bahwa setiap simpul memiliki derajat luar paling banyak 2. Asumsi ini konsisten dengan konvensi kami bahwa simpul mewakili satu instruksi. Kedua, kita berasumsi bahwa dag memiliki tepat satu simpul akar dengan derajat dalam 0 dan satu simpul terakhir dengan derajat luar 0 .

Kami menyajikan implementasi non-pemblokiran dari algoritma pencurian kerja [8], dan kami menganalisis kinerja pencuri kerja non-pemblokiran ini di lingkungan multiprogram. Dalam implementasi ini, semua struktur data bersamaan tidak memblokir [23,24] sehingga jika kernel mendahului suatu proses, itu tidak menghalangi pro-

cesses, misalnya dengan memegang kunci. Selain itu, implementasi ini memanfaatkan panggilan sistem "hasil" yang membatasi musuh kernel dengan cara yang memodelkan perilaku panggilan sistem hasil yang ditemukan di sistem operasi multiprosesor saat ini. Kami menunjukkan bahwa untuk setiap komputasi multithreaded dengan panjang pekerjaan

T_{1}

dan jalur kritis

T_{\infty}

, pencuri kerja non-pemblokiran berjalan dalam waktu yang

O (T_{1} / P_{A} + T_{\infty} P / P_{A})

diharapkan. Batas ini optimal dalam faktor konstan dan mencapai percepatan linier - yaitu, waktu

O (T_{1} / P_{A})

eksekusi - kapan pun

P = O (T_{1} / T_{\infty})

. Kami juga menunjukkan bahwa untuk setiap ,

ε > 0

dengan probabilitas setidaknya,

1 - ε

waktu eksekusi adalah

O (T_{1} / P_{A} + (T_{\infty} + \lg (1 / ε)) P / P_{A})

Hasil ini meningkat dari hasil sebelumnya [8] dalam dua cara. Pertama, kami mempertimbangkan perhitungan multithreaded arbitrer sebagai lawan dari kasus khusus komputasi "sepenuhnya ketat". Kedua, kami mempertimbangkan lingkungan multiprogram sebagai lawan dari lingkungan khusus. Lingkungan multiprogram adalah generalisasi dari lingkungan khusus, karena kita dapat melihat lingkungan khusus sebagai lingkungan multiprogram di mana kernel mengeksekusi komputasi pada

P

prosesor khusus. Selain itu, perhatikan bahwa dalam hal ini, kami memiliki

P_{A} = P

, dan ikatan kami untuk lingkungan multiprogram mengkhususkan diri untuk mencocokkan batas yang

O (T_{1} / P + T_{\infty})

ditetapkan sebelumnya untuk perhitungan yang sepenuhnya ketat yang dijalankan di lingkungan khusus.

Pencuri kerja non-pemblokiran kami telah diimplementasikan dan banyak studi kinerja telah dilakukan [9]. Studi ini menunjukkan bahwa kinerja aplikasi sesuai dengan

O (T_{1} / P_{A} +

T_{\infty} P / P_{A})

batas dan bahwa konstanta yang tersembunyi dalam notasi big-Oh kecil, kira-kira 1 . Selain itu, studi ini menunjukkan bahwa struktur data nonblocking dan penggunaan hasil sangat penting dalam praktiknya. Jika salah satu dari mekanisme implementasi ini dihilangkan, maka kinerja menurun secara dramatis untuk

P_{A} < P

.

Sisa makalah ini disusun sebagai berikut. Di Bagian 2, kami memformalkan model lingkungan multiprogram kami. Kami juga membuktikan batas bawah yang menyiratkan bahwa kinerja pencuri kerja nonblocking optimal dalam faktor konstan. Kami menyajikan pencuri kerja non-pemblokiran di Bagian 3, dan kami membuktikan lema struktural penting yang diperlukan untuk analisis. Pada Bagian 4 kami menetapkan batas atas yang optimal pada kinerja pencuri kerja di bawah berbagai asumsi sehubungan dengan kernel. Dalam Bagian 5, kami mempertimbangkan pekerjaan terkait. Dalam Bagian 6 kami menawarkan beberapa komentar penutup.

2 Multiprogramming

Wc memodelkan lingkungan multiprogram dengan kernel yang berperilaku sebagai musuh. Sedangkan penjadwal tingkat pengguna memetakan utas ke kumpulan

P

proses tetap, penjadwal tingkat kernel memetakan proses ke prosesor. Di bagian ini, kami mendefinisikan jadwal eksekusi, dan kami membuktikan batas atas dan bawah pada lamanya jadwal eksekusi. Batas-batas ini mudah dan disertakan terutama untuk memberi pembaca pemahaman yang lebih baik tentang model komputasi dan masalah sentral yang ingin kami tangani. Batas bawah menunjukkan optimalitas batas

O (T_{1} / P_{A} + T_{\infty} P / P_{A})

atas yang akan kita tetapkan untuk pencuri kerja non-pemblokiran kita.

Kernel beroperasi dalam langkah-langkah diskrit, diberi nomor dari 1, sebagai berikut. Pada setiap langkah

i

, kernel memilih subset

P

proses, dan kemudian proses yang dipilih ini diizinkan untuk mengeksekusi satu instruksi. Kami membiarkan

p_{i}

menunjukkan jumlah proses yang dipilih, dan kami mengatakan bahwa proses ini

p_{i}

dijadwalkan pada langkah

i

. Kernel dapat memilih untuk menjadwalkan sejumlah proses antara 0 dan

P

, jadi

0 \leq p_{i} \leq P

. Kita dapat melihat kernel sebagai menghasilkan jadwal kernel yang memetakan setiap bilangan bulat positif ke subset proses. Artinya, jadwal kernel memetakan setiap langkah

i

ke kumpulan proses yang dijadwalkan pada langkah

i

, dan

p_{i}

merupakan ukuran set tersebut.

Rata-rata

P_{A}

prosesor atas

T

langkah didefinisikan sebagai

P_{A} = \frac{1}{T} \sum_{i = 1}^{T} p_{i}

Meskipun analisis kami didasarkan pada model eksekusi sinkron langkah demi langkah ini, pencuri kerja kami tidak sinkron dan tidak bergantung pada sinkronisasi untuk kebenaran. Model sinkron mengakui kemungkinan bahwa pada satu langkah

i

, dua atau lebih proses dapat mengeksekusi instruksi yang mereferensikan lokasi memori umum. Kami berasumsi bahwa efek langkah

i

setara dengan beberapa eksekusi serial dari instruksi yang

p_{i}

dieksekusi oleh proses terjadwal

p_{i}

, di mana urutan eksekusi ditentukan dengan cara yang sewenang-wenang oleh kernel.

Mengingat jadwal kernel, jadwal eksekusi menentukan, untuk setiap langkah

i

, subset tertentu dari node yang paling siap

p_{i}

untuk dieksekusi oleh proses terjadwal

p_{i}

pada langkah

i

. Kami mendefinisikan panjang jadwal eksekusi menjadi jumlah langkah dalam jadwal. Jadwal eksekusi ditentukan baik oleh penjadwal tingkat pengguna maupun oleh kernel. Secara khusus, penjadwal tingkat pengguna on-line tidak mengetahui jadwal kernel untuk langkah-langkah mendatang. Pada setiap langkah, penjadwal tingkat pengguna dapat menentukan instruksi apa yang harus dijalankan proses selanjutnya, tetapi tidak memiliki cara untuk menentukan kapan kernel benar-benar akan membiarkan proses mengeksekusi instruksi berikutnya.

Teorema berikut menunjukkan bahwa

T_{1} / P_{A}

dan

T_{\infty} P / P_{A}

keduanya merupakan batas bawah pada panjang jadwal eksekusi apa pun. Batas bawah

T_{1} / P_{A}

penahanan terlepas dari jadwal kernel, sedangkan batas bawah

T_{\infty} P / P_{A}

penahanan hanya untuk beberapa jadwal kernel. Artinya, ada jadwal kernel sedemikian rupa sehingga setiap jadwal eksekusi memiliki panjang setidaknya

T_{\infty} P / P_{A}

. Selain itu, ada jadwal kernel seperti itu dengan

P_{A}

mulai dari

P

turun hingga nilai yang sewenang-wenang mendekati 0 . Batas bawah ini menyiratkan batas bawah yang sesuai pada performa penjadwal tingkat pengguna apa pun.

Teorema 1 Pertimbangkan setiap komputasi multithreaded dengan panjang kerja

T_{1}

dan jalur kritis

T_{\infty}

, dan sejumlah

P

proses. Kemudian untuk jadwal kernel apa pun, setiap jadwal eksekusi memiliki panjang setidaknya

T_{1} / P_{A}

, di mana

P_{A}

rata-rata prosesor selama durasi jadwal. Selain itu, untuk sejumlah

P_{A}^{'}

bentuk

T_{\infty} P / (k + T_{\infty})

di mana

k

bilangan bulat nonnegatif, ada jadwal kernel sedemikian rupa sehingga setiap jadwal eksekusi memiliki panjang setidaknya

T_{\infty} P / P_{A}

, dan

P_{A}

berada dalam kisaran

⌊ P_{A}^{'} ⌋ \leq P_{A} \leq P_{A}^{'}

.

Bukti: Rata-rata prosesor selama durasi

T

jadwal ditentukan oleh Persamaan (1), jadi kita memiliki

T = \frac{1}{P_{A}} \sum_{i = 1}^{T} p_{i}

Untuk kedua batas bawah, kita terikat

T

dengan batas

\sum_{i = 1}^{T} p_{i}

. Batas bawah langsung

T_{1} / P_{A}

dari batas

\sum_{i = 1}^{T} p_{i} \geq T_{1}

bawah , yang mengikuti fakta bahwa jadwal eksekusi apa pun diperlukan untuk mengeksekusi semua node dalam komputasi multithreaded. Untuk batas bawah ,

T_{\infty} P / P_{A}

kami membuktikan batas

\sum_{i = 1}^{T} p_{i} \geq T_{\infty} P

bawah .

Kami membangun jadwal kernel yang memaksa setiap jadwal eksekusi untuk memenuhi batas ini sebagai berikut. Biarlah

k

seperti yang didefinisikan dalam pernyataan lemma. Jadwal kernel ditetapkan

p_{i} = 0

untuk

1 \leq i \leq k

, set untuk

p_{i} = P

k + 1 \leq i \leq k + T_{\infty}

, dan set untuk

p_{i} = [P_{A}^{'} ⌋

k + T_{\infty} < i

. Setiap jadwal eksekusi memiliki panjang

T \geq k + T_{\infty}

, jadi kita memiliki batas

\sum_{i = 1}^{T} p_{i} \geq T_{\infty} P

bawah . Tetap hanya untuk menunjukkan bahwa berada

P_{A}

dalam kisaran yang diinginkan. Rata-rata prosesor untuk langkah pertama

k + T_{\infty}

adalah

T_{\infty} P / (k + T_{\infty}) = P_{A}^{'}

. Untuk semua langkah

i > k + T_{\infty}

selanjutnya, kami memiliki

p_{i} = ⌊ P_{A}^{'} ⌋

. Dengan demikian,

P_{A}

berada dalam kisaran yang diinginkan.

Kita mengatakan bahwa jadwal eksekusi itu serakah jika pada setiap langkah

i

jumlah node siap yang dieksekusi sama dengan minimum dan

p_{i}

jumlah simpul siap. Perhatikan bahwa penjadwal tingkat pengguna online tidak selalu dapat menghasilkan jadwal eksekusi yang serakah, karena sejumlah overhead penjadwalan seringkali tidak dapat dihindari. Teorema berikut tentang jadwal eksekusi serakah juga berlaku untuk jadwal eksekusi tingkat demi tingkat (Brent [10]), dengan hanya perubahan sepele pada bukti.

Teorema 2 (Jadwal Serakah) Pertimbangkan komputasi multithreaded dengan pekerjaan

T_{1}

dan panjang

T_{\infty}

jalur kritis, sejumlah

P

proses, dan jadwal kernel apa pun. Setiap jadwal eksekusi serakah memiliki panjang paling banyak

T_{1} / P_{A} + T_{\infty} (P - 1) / Γ_{A}

, di mana

P_{A}

rata-rata prosesor selama durasi jadwal.

Bukti: Pertimbangkan jadwal eksekusi yang serakah, dan biarkan

T

menunjukkan panjangnya. Seperti dalam pembuktian Teorema 1, kita terikat

T

dengan membatasi

\sum_{i = 1}^{T} p_{i}

. Untuk setiap langkah

i = 1, \dots, T

, kami mengumpulkan

p_{i}

token, satu dari setiap proses yang dijadwalkan pada langkah

i

, dan kemudian kami mengikat jumlah total token yang dikumpulkan. Selain itu, kami mengumpulkan token dalam dua ember: ember kerja dan ember idle. Pertimbangkan langkah

i

dan proses yang dijadwalkan pada langkah

i

. Jika proses mengeksekusi node komputasi, maka ia menempatkan tokennya ke dalam bucket kerja, dan jika tidak, kita mengatakan bahwa proses tersebut menganggur dan menempatkan tokennya ke dalam bucket idle. Setelah langkah terakhir, bucket kerja berisi token tepat

T_{1}

- satu token untuk setiap simpul komputasi. Tetap hanya untuk membuktikan bahwa bucket idle berisi paling banyak

T_{\infty} (P -

1) token.

Pertimbangkan langkah di mana beberapa proses menempatkan token di bucket idle. Kami menyebut langkah seperti itu sebagai langkah menganggur. Pada langkah idle kita memiliki proses idle dan karena jadwalnya serakah, maka setiap node yang siap dieksekusi pada langkah idle. Pengamatan ini mengarah pada dua pengamatan lebih lanjut. Pertama, pada setiap langkah setidaknya ada satu node siap, jadi dari proses yang

p_{i}

dijadwalkan pada langkah

i

idle , paling banyak

p_{i} - 1 \leq P - 1

bisa menganggur. Kedua, untuk setiap langkah

i

, mari kita

G_{i}

tunjukkan sub-dag komputasi yang hanya terdiri dari simpul yang belum dieksekusi setelah langkah

i

. Jika langkah adalah

i

langkah idle, maka setiap node dengan derajat 0 akan

G_{i - 1}

dieksekusi pada langkah

i

, jadi jalur terpanjang di adalah

G_{i}

satu node lebih pendek dari jalur terpanjang di

G_{i - 1}

. Karena jalur terpanjang memiliki

G_{0}

panjang

T_{\infty}

, paling banyak

T_{\infty}

ada anak tangga yang menganggur. Menyatukan kedua pengamatan ini, kami menyimpulkan bahwa setelah langkah terakhir, bucket idle berisi paling banyak

T_{\infty} (P - 1)

token.

Teorema 1 dan 2 menunjukkan bahwa untuk beberapa jadwal kernel, setiap jadwal eksekusi serakah berada dalam faktor dua optimal. Selain itu, meskipun kami tidak akan membuktikannya, untuk jadwal kernel apa pun, beberapa jadwal eksekusi serakah optimal. Kami berkomentar bahwa fakta terakhir tidak menyiratkan keberadaan algoritma waktu polinomial untuk menghitung jadwal eksekusi yang optimal. Faktanya, masalah keputusan terkait adalah NP-complete [33].

3 Mencuri pekerjaan non-pemblokiran

Pada bagian ini kita meninjau algoritma pencurian kerja [8], dan kemudian menjelaskan implementasi non-pemblokiran kita, yang melibatkan penggunaan panggilan sistem hasil dan implementasi non-pemblokiran dari struktur data bersamaan. Kami menyimpulkan bagian ini dengan "lema struktural" penting yang digunakan dalam analisis kami.

3.1 Algoritma pencurian kerja

Dalam algoritma pencurian kerja, setiap proses mempertahankan kumpulan utas siap pakainya sendiri dari mana ia memperoleh pekerjaan. Jika kumpulan proses menjadi kosong, proses itu menjadi pencuri dan mencuri benang dari kumpulan proses korban yang dipilih secara acak. Setiap kumpulan utas dipertahankan sebagai antrean ujung ganda, atau deque, yang memiliki bagian bawah dan bagian atas.

Untuk mendapatkan pekerjaan, sebuah proses memunculkan thread siap dari bagian bawah deque-nya dan mulai mengeksekusi thread tersebut. Proses

terus mengeksekusi utas itu sampai utas memblokir atau mengakhiri, di mana proses kembali ke deque untuk mendapatkan utas siap lainnya. Selama menjalankan utas, jika utas membuat utas baru atau membuka blokir utas yang diblokir, maka proses tersebut mendorong utas yang baru siap ke bagian bawah deque-nya. Sebagai alternatif, proses dapat mendahului thread yang sedang dikerjakan, mendorong thread tersebut ke bagian bawah diske-nya, dan mulai mengeksekusi thread yang baru siap. Alternatif ini mengakui pengoptimalan dalam manajemen utas seperti pembuatan tugas malas [18, 19, 27]. Selama deque suatu proses tidak kosong, proses memanipulasi deque dengan cara LIFO (stack-like).

Ketika sebuah proses pergi untuk mendapatkan pekerjaan dengan mengeluarkan benang dari bagian bawah deque-nya, jika menemukan bahwa deque-nya kosong, maka proses tersebut menjadi pencuri. Ini memilih proses korban secara acak (menggunakan distribusi yang seragam) dan mencoba untuk mendapatkan pekerjaan dengan menghilangkan benang di bagian atas deque proses korban. Jika deque proses korban kosong, maka pencuri memilih proses korban lain dan mencoba lagi. Pencuri berulang kali mencoba mencuri sampai menemukan korban yang deque tidak kosong, di mana pencuri "reformasi" (yaitu, berhenti menjadi pencuri) dan mulai mengerjakan benang yang dicuri seperti yang dijelaskan di atas. Karena pencurian terjadi di bagian atas deque korban, pencurian beroperasi dengan cara FIFO.

Detail penjadwal pencurian pekerjaan kami disajikan pada Gambar 1. Dalam implementasi non-pemblokiran kami, setiap proses melakukan panggilan sistem hasil antara setiap pasangan upaya pencurian berturut-turut. Kami menjelaskan semantik panggilan sistem yield nanti di Bagian 4.4. Panggilan sistem ini tidak diperlukan untuk kebenaran, tetapi seperti yang akan kita lihat di Bagian 4.4, hasil kadang-kadang diperlukan untuk mencegah kernel kelaparan proses.

3.2 Spesifikasi metode deque

Pada bagian ini kami mengembangkan spesifikasi untuk objek deque, yang dibahas secara informal di atas. Deque mendukung tiga metode: pushBottom, popBottom, dan popTop. Metode pushTop tidak didukung, karena tidak diperlukan oleh algoritma pencurian kerja. Implementasi deque didefinisikan menjadi konstan-waktu jika dan hanya jika masing-masing dari tiga metode berakhir dalam jumlah instruksi yang konstan. Di bawah ini kami mendefinisikan semantik "ideal" dari metode ini. Setiap implementasi deque waktu konstan yang memenuhi semantik ideal bebas menunggu [24]. Sayangnya, kami tidak mengetahui implementasi deque bebas menunggu waktu konstan. Untuk alasan ini, kita melanjutkan untuk mendefinisikan semantik "santai" untuk metode deque. Setiap implementasi deque waktu konstan yang memenuhi semantik santai adalah non-pemblokiran [23,24] dan cukup bagi kita untuk membuktikan batas kinerja kita.

Sekarang kita mendefinisikan semantik deque yang ideal. Untuk melakukannya, pertama-tama kita mendefinisikan apakah serangkaian pemanggilan metode deque yang diberikan memenuhi semantik yang ideal. Kami melihat pemanggilan metode deque sebagai 4 -tuple yang menentukan: (i) nama metode deque yang dipanggil (yaitu, pushBottom, popBottom, atau popTop), (ii) waktu inisiasi, (iii) waktu penyelesaian, dan (iv) nilai pengembalian (jika ada). Satu set pemanggilan memenuhi semantik ideal jika dan hanya jika ada waktu linearisasi untuk setiap pemanggilan sehingga: (i) waktu linearisasi terletak antara waktu inisiasi dan waktu penyelesaian, (ii) tidak ada dua waktu linearisasi yang bertepatan, dan (iii) nilai yang dikembalikan konsisten dengan eksekusi serial dari pemanggilan metode dalam urutan yang diberikan oleh waktu linearisasi. Implementasi deque memenuhi semantik ideal jika dan hanya jika untuk eksekusi apa pun, kumpulan pemanggilan terkait memenuhi semantik ideal. Kami berkomentar bahwa implementasi deque memenuhi semantik ideal jika dan hanya jika masing-masing dari tiga metode deque dapat dilinierisasi, seperti yang didefinisikan dalam [22].

Lebih mudah untuk mendefinisikan serangkaian pemanggilan menjadi baik jika dan hanya jika tidak ada dua pemanggilan pushBottom atau popBottom yang bersamaan. Perhatikan bahwa setiap set pemanggilan yang terkait dengan beberapa eksekusi algoritma pencurian kerja adalah baik karena pemilik (unik) dari setiap deque adalah satu-satunya proses yang pernah melakukan pushBottom atau popBottom pada deque itu. Jadi, untuk saat ini-

Penelitian ini sebagian didukung oleh Defense Advanced Research Projects Agency (DARPA) di bawah Hibah F30602-97-1-0150 dari Laboratorium Penelitian Angkatan Udara AS. Selain itu, Greg Plaxton didukung oleh National Science Foundation di bawah Grant CCR-9504145. Fasilitas komputasi multiprosesor disediakan melalui sumbangan murah hati oleh Sun Microsystems.

Izin untuk membuat salinan digital atau cetak dari semua atau sebagian dari karya ini untuk penggunaan pribadi atau kelas diberikan tanpa biaya asalkan salinan tidak dibuat atau didistribusikan untuk keuntungan atau keuntungan komersial dan salinan tersebut memiliki pemberitahuan ini dan kutipan lengkap di halaman pertama. Untuk menyalin sebaliknya, menerbitkan ulang, memposting di server atau mendistribusikan ulang ke daftar, memerlukan izin khusus sebelumnya dan/atau biaya.

SPAA 98 Puerto Vallarta Meksiko

Hak Cipta ACM 1998 0-89791-989-0/98/6...$5.00