Apakah ada mesin abstrak yang dapat menangkap konsumsi daya?

13

Ketika melaporkan kompleksitas algoritmik suatu algoritma, seseorang mengasumsikan perhitungan yang mendasarinya dilakukan pada beberapa mesin abstrak (misalnya RAM) yang mendekati CPU modern. Model semacam itu memungkinkan kami melaporkan kompleksitas algoritma waktu dan ruang. Sekarang, dengan penyebaran GPGPU , orang bertanya-tanya apakah ada model terkenal di mana orang dapat memperhitungkan konsumsi daya juga.

GPU dikenal mengkonsumsi banyak daya dan instruksi tertentu termasuk dalam kategori konsumsi daya yang berbeda berdasarkan kompleksitas dan lokasinya pada chip yang canggih. Oleh karena itu instruksi, dari sudut pandang energi, bukan dari biaya satuan (atau bahkan tetap). Perpanjangan sepele akan menetapkan bobot untuk biaya operasi, tapi saya mencari model yang kuat di mana operasi / instruksi mungkin memakan biaya unit energi yang tidak konstan , misalnya jumlah polinomial (atau bahkan lebih kompleks misalnya: fungsi waktu berlalu sejak awal algoritma, atau memperhitungkan kemungkinan kegagalan sistem pendingin, yang akan memanaskan chip, dan memperlambat frekuensi clock dll.)

Apakah ada model seperti itu di mana biaya dan kesalahan non-sepele dapat dimasukkan?

complexity-theory computer-architecture power-consumption machine-models Gopi
sumber

Apakah Anda memiliki alasan untuk percaya bahwa jumlah energi yang ada pada biaya operasi dasar dapat berubah (kompleks)? Jika Anda tertarik, saya tahu tentang pekerjaan yang menganalisis konsumsi energi dengan alat teoretis.

Raphael

8

Belum ada model yang mapan, tetapi ini adalah area penelitian aktif saat ini. Salah satu ahli di sisi algoritma adalah Kirk Pruhs. Makalahnya memiliki informasi lebih lanjut, dan Anda juga dapat menelusuri presentasi ini .

Suresh
sumber

Saya tidak setuju dengan kenyataan bahwa belum ada model yang mapan: sebagian besar makalah setuju pada model fisik yang rumit, mereka hanya fokus pada bagian yang berbeda dari model fisik ini. Untuk beberapa kasus, Kirk berfokus pada energi dinamis.

Gopi

Saya kira maksud saya tidak ada model biaya komputasi yang mapan.

Suresh

7

Model untuk konsumsi energi

Penskalaan kecepatan adalah salah satu model yang paling sering digunakan (baru-baru ini) ketika mempertimbangkan konsumsi energi. Terdiri dalam memodifikasi tegangan suplai. Dengan menurunkan tegangan suplai, atau frekuensi clock prosesor, dimungkinkan untuk mencapai pengurangan penting dalam konsumsi daya; kecepatan yang lebih cepat memungkinkan untuk eksekusi yang lebih cepat, tetapi mereka juga mengarah pada konsumsi daya yang jauh lebih tinggi (supra-linear).

$s$ $s^3$ $s^3 \times d$ $d$

Namun penskalaan kecepatan bukan satu-satunya energi yang dipertimbangkan. Inilah yang disebut energi dinamis . The statis energi adalah kekuatan yang disebabkan oleh prosesor makhluk 'on'. Dimungkinkan untuk menghilangkan daya statis ini dengan mematikan prosesor selama waktu idle. Namun ada biaya. Ada banyak pekerjaan yang dilakukan pada subjek ini yang sangat dekat dengan masalah penyewaan ski .

Biasanya konsumsi energi adalah jumlah dari konsumsi daya statis dan dinamis dikalikan waktu pelaksanaan. Namun, sebagian besar kertas fokus pada salah satu dari masalah ini.

Memperkenalkan kesalahan dalam model ini

Saya pikir ini adalah bagian paling mengejutkan dari model penskalaan kecepatan. Biasanya orang akan berpikir bahwa semakin cepat Anda menjalankan tugas, semakin besar kemungkinan Anda gagal menjalankannya. Sebaliknya, itu menunjukkan bahwa mengurangi kecepatan prosesor meningkatkan jumlah tingkat kesalahan transien sistem; probabilitas kegagalan meningkat secara eksponensial, dan probabilitas ini tidak dapat diabaikan dalam komputasi skala besar.

Secara intuitif, ada fakta bahwa semakin banyak waktu yang Anda habiskan untuk suatu tugas, semakin banyak peluang Anda harus gagal selama pelaksanaan tugas itu. Namun ada lebih dari itu: Shatz dan Wang dalam hal ini , menyatakan bahwa model kesalahan mengikuti distribusi Poisson. Parameter dari distribusi Poisson adalah: \ mana adalah kecepatan pemrosesan yang terdiri dari , dan dan bergantung konstan pada systyem. Jika Anda mempertimbangkan tugas bobot , dijalankan pada kecepatan , keandalan eksekusi untuk tugas itu adalah $\lambda$

λ (f) = λ_{0} e^{d \frac{f m a x - f}{f m a x - f m i n}},

$\lambda(f)=\lambda_0 e^{d\frac{fmax-f}{fmax-fmin}},$

f

$f$

[f m i n, f m a x]

$[fmin,fmax]$

λ_{0}

$\lambda_0$

d

$d$

w

$w$

f

$f$

R (f) = e^{- λ (f) \times \frac{w}{f}}

$R(f)=e^{-\lambda(f)\times\frac{w}{f}}$ .

Ini adalah referensi sendiri jadi saya tidak tahu apakah itu dihargai di sini, namun jika Anda tertarik, Anda dapat menemukan informasi lebih lanjut dalam makalah ini pada bagian dinamis dari konsumsi energi.

Gopi
sumber

3

Sudah ada upaya untuk menganalisis konsumsi energi dari algoritma dalam teori (tentu saja menggunakan biaya kehidupan nyata per operasi); lihat misalnya [1]. Walaupun hasilnya cukup mengejutkan --- algoritma tercepat tidak selalu menggunakan sedikit energi --- beberapa kendala tetap ada.

Khususnya, platform modern mematikan fitur tertentu sehingga biaya energi operasi lonjakan ketika dihidupkan lagi. Walaupun pada prinsipnya memungkinkan untuk dimasukkan dalam analisis yang ketat, secara teknis (juga?) Menjadi sulit. Juga, efek cache yang hilang pada konsumsi energi total belum diteliti dengan baik.

Tampaknya perbedaan besar antara platform menentang analisis yang ketat yang dapat (untuk sekali) tidak mengabaikan spesifik karena model umum (yaitu sebelum memasukkan konstanta / fungsi beton) memiliki signifikansi yang terbatas.

Hannah Bayer dan Markus E. Nebel: Mengevaluasi Algoritma sesuai dengan Konsumsi Energi , Komputasi di Eropa, 2009

Raphael
sumber

Apakah ada mesin abstrak yang dapat menangkap konsumsi daya?

Jawaban: