Gagasan formal untuk kompleksitas energi dari masalah komputasi

Kompleksitas komputasi mencakup studi kompleksitas ruang atau waktu dari masalah komputasi. Dari perspektif komputasi mobile, energi adalah sumber daya komputasi yang sangat berharga. Jadi, Adakah adaptasi yang dipelajari dengan baik dari mesin Turing yang memperhitungkan energi yang dikonsumsi selama eksekusi algoritma. Juga, Apakah ada kelas kompleksitas energi yang ditetapkan untuk masalah komputasi?

Referensi dihargai.

Apakah ada adaptasi yang dipelajari dengan baik dari mesin Turing yang memperhitungkan energi yang dikonsumsi selama eksekusi algoritma? Tidak!

Tapi mungkin Anda bisa membuat satu. Mungkin saja Anda dapat membagi langkah-langkah mesin Turing menjadi reversibel dan non-reversibel (yang non-reversibel adalah saat informasi hilang). Secara teoritis, hanya langkah-langkah non-reversibel yang menghabiskan energi. Biaya satu unit energi untuk setiap bit yang dihapus secara teori akan menjadi ukuran yang tepat.

$kT\, \ln 2$$T$$k$$\alpha$$\beta$

Saya tidak tahu bagaimana mesin Turing dengan beberapa langkah reversibel berhubungan dengan chip dengan beberapa sirkuit reversibel, tapi saya pikir kedua model layak diselidiki.

Belum ada kelas kompleksitas energi, tetapi pasti ada banyak minat dalam mempelajari cara merancang algoritma yang hemat energi dalam beberapa model. Saya tidak akrab dengan seluruh tubuh pekerjaan, tetapi satu titik masuk adalah pekerjaan yang dilakukan Kirk Pruhs pada komputasi berkelanjutan. Kirk adalah seorang ahli teori dengan keahlian dalam penjadwalan dan perkiraan, dan baru-baru ini menjadi sangat aktif di bidang ini, sehingga perspektifnya bagus untuk orang-orang algoritmik.

ps poin gabgoh tentang prinsip Landauer adalah bagus. Jika Anda ingin mempelajari lebih lanjut tentang hubungan antara energi dan informasi, tidak ada sumber yang lebih baik daripada buku Demon Maxwell .

Ini bukan jawaban langsung sama sekali, tetapi ada beberapa koneksi yang berpotensi berguna untuk menggambar / meneliti program yang akan dilakukan di sepanjang garis Stay dan karya Baez 'pada termodinamika algoritmik: http://johncarlosbaez.wordpress.com/2010/10 / 12 / algoritmik-termodinamika /

Namun perlu diperhatikan bahwa karya ini tidak menarik konsekuensi fisik yang sebenarnya - melainkan menggambarkan hubungan yang, sejauh ini, murni matematis.

Kei Uchizawa dan rekan penulisnya mempelajari kompleksitas energi dari ambang batas sirkuit. Mereka mendefinisikannya sebagai jumlah maksimum ambang gerbang yang menghasilkan 1 atas semua input yang mungkin.

Karena ini bukan tentang mesin Turing, ini tidak menjawab pertanyaan. Tapi, saya harap makalah mereka memberikan beberapa ide. Halaman webnya berisi pointer. http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/

Ada beberapa pembenaran untuk menggunakan model memori eksternal sebagai model perhitungan yang sadar energi. Paolo Ferragina membahas ini secara singkat dalam pidatonya yang diundang di ESA 2010, tetapi saya tidak tahu apakah ada hasil yang dipublikasikan. Ide dasarnya adalah bahwa jika jumlah I / O mendominasi waktu perhitungan, maka energi yang diperlukan untuk I / O tersebut mungkin akan mendominasi total konsumsi energi.

The laporan dari Lokakarya Pertama di Ilmu Manajemen Daya terutama yang terdapat pertanyaan dan masalah terbuka. Saya tidak tahu apa yang terjadi pada Lokakarya Kedua , tetapi halaman web mengatakan bahwa akan ada masalah khusus tentang Komputasi Berkelanjutan yang didedikasikan untuk pendekatan teoretis, matematis, dan algoritmik untuk komputasi berkelanjutan.

berikut adalah beberapa referensi / sudut pandang yang lebih baru / lainnya tentang pertanyaan yang tampaknya dalam ini dengan penelitian yang sedang berlangsung. seperti yang ditunjukkan oleh P.Shor daerah sejauh ini tampaknya menunggu survei komprehensif, standardisasi, dan / atau unifikasi. ada pendekatan yang lebih abstrak / teoretis yang tercantum di urutan ke-1, diikuti oleh pendekatan yang lebih diterapkan: algoritma hemat energi, pengukuran penggunaan energi di ponsel untuk penyortiran, studi faktor-faktor dalam VLSI yang memengaruhi kompleksitas energi / waktu.

• Model kompleksitas energi untuk algoritma, Swapnoneel Roy Atri Rudra Akshat Verma ITCS 2013

• Menuju kompleksitas energi komputasi Alain J. Martin, IPL 2001

• Kompleksitas vs Energi: Teori Komputasi dan Fisika Teoritis Yuri I. Manin

• Menuju Model Kompleksitas Energi untuk Algoritma Ravi Jain, David Molnar, Zulfikar Ramzan

• Algoritma Hemat Energi Susanne Albers

• Yao, FF, Demers, AJ, Shenker, S. Model penjadwalan untuk mengurangi energi CPU. Dalam Prosiding Simposium IEEE ke-36 tentang Yayasan Ilmu Komputer (1995), 374-382.

• Menjelajahi Konsumsi Energi dari Algoritma Penyortiran Data di Lingkungan Tertanam dan Bergerak Christian Bunse Hagen Ho ̈pfner Essam Mansour Suman Roychoudhury

• Kompleksitas Algoritma Energi-Waktu: Pemodelan trade-off CMOS VLSI (2007) oleh Brad D. Bingham

Kompleksitas waktu dan ruang tidak tergantung pada perangkat. Saya tidak melihat cara untuk membuat perangkat kompleksitas energi independen.

$W$$W$$W$

$O(W f(n)) = O(f(n))$