Apakah algoritma tergantung pada arsitektur komputer?

Saya membaca di suatu tempat (lupa buku mana itu) bahwa algoritma tidak tergantung pada arsitektur komputer. Beberapa bahkan mengatakan algoritma itu sendiri komputasi (mesin?)?

Di sisi lain, buku tentang pemrograman paralel memiliki bab tentang algoritma paralel. Sepertinya algoritma paralel bergantung pada arsitektur paralel?

Saya pikir saya kehilangan beberapa foto besar? Terima kasih.

Algoritma adalah serangkaian langkah yang diambil untuk memecahkan masalah tertentu. Resep untuk memecahkan masalah, jika Anda mau. "Program" melakukan hal yang sama, tentu saja; kami menggunakan "algoritma" untuk menyarankan resep "umum" atau "yang berlaku umum" yang tidak tergantung pada desain mesin, bahasa pemrograman, dan semacamnya.

Algoritma dimaksudkan untuk bersifat umum, tetapi mereka masih dapat bergantung pada beberapa fitur yang ada. "Algoritma bersamaan," misalnya, mungkin bergantung pada Anda memiliki beberapa mekanisme untuk menjalankan berbagai program secara bersamaan. "Algoritma terdistribusi" dapat bergantung pada Anda memiliki lebih dari satu sistem dalam kelompok yang bekerja sama, dan jaringan atau skema komunikasi lainnya di antara mereka. Demikian pula, "algoritma paralel" sering kali dirancang untuk dijalankan ketika Anda memiliki beberapa unit pemrosesan - berpotensi banyak, banyak unit pemrosesan, dan jenis fasilitas komunikasi yang umum ketika Anda memiliki array besar unit pemrosesan. Anda mungkin dapat menjalankan "algoritma paralel" bahkan ketika Anda hanya memiliki satu komputer atau satu CPU - tetapi itu tidak terlalu menarik dalam hal memiliki insinyur lalu lintas tidak

Algoritma tidak tergantung pada arsitektur komputer. Itu karena algoritma mendefinisikan serangkaian proses yang memecahkan masalah. Terlepas dari arsitektur, algoritma pengurutan akan selalu mengurutkan. Itu tidak akan tiba-tiba membuat gambar 3D pada beberapa arsitektur.

Jika Anda memikirkannya, ini sebenarnya intuitif. Google Chrome (yang hanya kumpulan algoritma) adalah browser web ketika dikompilasi untuk arsitektur apa pun. Itu tidak akan tiba-tiba menjadi driver perangkat pada beberapa arsitektur.

Tetapi kecepatan menjalankan algoritma tergantung pada arsitektur. Dan beberapa algoritma bekerja lebih cepat daripada yang lain tergantung pada arsitektur.

Jika Anda memikirkannya, ini juga sebenarnya intuitif. Dengan algoritma, selalu memungkinkan bagi perancang perangkat keras untuk merancang arsitektur yang secara khusus mempercepat algoritme itu. Itulah salah satu alasan mengapa ada hal-hal seperti akselerasi kartu grafis 3D dan akselerator penambang bitcoin.

Ketika orang berbicara tentang algoritma paralel, mereka berbicara tentang keluarga algoritma yang dapat bekerja lebih cepat pada arsitektur paralel. Ada banyak algoritma yang tidak ditingkatkan oleh arsitektur paralel. Jadi mengidentifikasi algoritma baru untuk masalah yang sama yang bekerja dengan baik secara paralel adalah area aktif penelitian.

Tetapi algoritma tersebut masih melakukan hal yang sama. Arsitektur tidak mengubah apa yang mereka lakukan.

"Sepertinya algoritma paralel bergantung pada arsitektur paralel?"

Menurut pendapat saya jawabannya sederhana: tidak. Secara umum saya hanya mendapatkan propertinya

• paralelisme
• ukuran kata (batas sumber daya implisit)

ketika memikirkan arsitektur perangkat keras.

Mengacu pada paralelisme, Anda dapat memiliki algoritma paralel yang dikomputasi secara batch dan setiap lengkung paralel yang berfungsi serial sehingga algoritme tidak bergantung pada hal itu. Ukuran kata mungkin menjadi masalah stabilitas numerik tetapi tidak pada algoritma itu sendiri. Batas sumber daya seperti 64bit hanya dapat menggambarkan 2 ^ 64 angka yang berbeda bisa menjadi masalah, tetapi elemen-elemennya terbatas.

Tentu saja mungkin ada beberapa algoritma yang tergantung pada beberapa set instruksi yang diperluas, tetapi setidaknya semuanya dapat dijelaskan dengan matematika dasar.

Sebagai contoh dengan komputasi kuantum beberapa nilai Big-O dapat berubah dan kemudian saya akan mengatakan itu

"Algoritma tidak tergantung pada arsitektur komputer"

sudah tidak benar lagi.

Algoritma tidak tergantung pada arsitektur komputer, namun efisiensi menjalankan algoritma tertentu bergantung pada arsitektur. Mesin Turing Lengkap dapat meniru mesin Turing Lengkap lainnya, meskipun beberapa mesin akan lebih baik pada satu hal daripada yang lain.

Apa yang kami maksudkan dengan algoritma konkuren adalah bahwa algoritme itu bekerja dengan baik atau dapat memanfaatkan konkurensi dalam mesin, mungkin karena membutuhkan penguncian yang lebih sedikit yang jika tidak diperlukan oleh algoritma yang tidak secara khusus dirancang untuk mesin bersamaan atau mungkin karena algoritma memanfaatkan divide dan conquer secara efektif untuk menggunakan kekuatan penuh mesin. Menjalankan algoritma dalam mesin non-konkuren masih dimungkinkan tetapi mungkin tidak seefisien atau mungkin memerlukan penguncian tambahan untuk melakukan dengan benar.

Ada juga algoritma yang dirancang untuk mengambil keuntungan dari kekhasan arsitektur tertentu, seperti algoritma cache-friendly, yang mengoptimalkan caching. Algoritma ini mungkin kurang efisien dalam mesin yang tidak men-cache cara yang diasumsikan algoritma.

Secara teori, algoritma sepenuhnya independen dari arsitektur. Anda selalu dapat meniru arsitektur paralel pada sistem timesliced ​​satu masalah. Anda dapat alasan tentang algoritma tanpa arsitektur sama sekali. Buku Knuth menggunakan arsitektur fiksi.

Dalam praktiknya ada algoritma yang berupaya mencapai runtime yang lebih baik untuk kompleksitas "O" yang sama dengan mengoptimalkan penggunaan perangkat keras cache dan sinkronisasi primitif.

Iya dan tidak. Itu tergantung pada kendala yang ingin Anda temui dan prasyarat yang diperlukan untuk menjalankan algoritma Anda.

Idealnya, suatu algoritma adalah resep abstrak yang mendefinisikan langkah-demi-langkah bagaimana melakukan sesuatu. Algoritma didefinisikan seperti itu dengan tujuan reproduktifitas, dan otomatisasi kemudian. Algoritma berasal dari perhitungan lambda, sehingga Anda dapat dengan mudah melihat mengapa mereka dibuat sedemikian rupa. Definisi ini adalah yang biasa, tetapi algoritma modern dapat non-sekuensial (bukan langkah-demi-langkah, seperti algoritma bersamaan, atau yang logis seperti yang menggunakan penyatuan), non-linear (algoritme stokastik) atau sekadar aneh (kuantum) algoritma), tapi saya akan melewati itu.

Jadi, idealnya, suatu algoritma harus seabstrak mungkin tanpa memperhitungkan perangkat keras apa pun.

Tetapi, seperti halnya sistem apa pun, Anda harus mendefinisikan beberapa aksioma , tidak hanya untuk mendapatkan sistem yang koheren, tetapi juga untuk mendapatkan waktu. Sebagai contoh, sebagian besar algoritma menganggap, paling tidak secara implisit, bahwa mereka didefinisikan pada mesin Von-Neumann. Jika bukan itu masalahnya, mereka perlu mendefinisikan secara eksplisit setiap bagian dari sistem yang mereka perlukan untuk dijalankan (karena ini diperlukan untuk mereproduksi resep, ini semacam prasyarat). Juga, seringkali algoritma bergantung pada perintah umum seperti write () tanpa mendefinisikannya sepenuhnya.

Alasan lain mengapa algoritma tidak begitu abstrak dari arsitektur perangkat keras, adalah ketika Anda perlu memenuhi beberapa kendala .

Katakanlah Anda bekerja pada sistem embedded, maka mungkin Anda tidak dapat mengandalkan jumlah sumber daya yang sama dengan yang Anda miliki di workstation. Salah satu sumber daya yang paling terkendali mungkin memori. Namun, sebagian besar algoritma cenderung mengoptimalkan kompleksitas waktu (kecepatan eksekusi pada CPU), bukan kompleksitas memori (jumlah memori yang diperlukan untuk mengerjakan data). Untuk sistem ini, algoritma yang dioptimalkan memori telah dirancang di mana algoritma yang dioptimalkan non-memori hanya akan gagal atau berjalan jauh lebih lambat. Faktanya, embedded system bukan satu-satunya target dari algoritma memory efisien: misalnya, ada algoritma cache-oblivious yang mengadaptasi pemrosesan mereka untuk secara efisien menggunakan cache CPU. Contoh lain: beberapa algoritma pembelajaran mesin untuk data besar dirancang untukpembelajaran tambahan atau komputasi out-of-core untuk memproses sejumlah besar data yang jauh lebih besar daripada memori yang tersedia di komputer mana pun, dll.

Ada juga algoritma yang tidak mengoptimalkan bagian tertentu dari komputer, tetapi standar yang bergantung pada arsitektur perangkat keras. Sebagai contoh, data numerik yang membutuhkan ketelitian disimpan di dalam float atau double, yang pada dasarnya terbatas karena batasan perangkat keras. Masalahnya adalah bahwa perhitungan yang rumit dapat menyebabkan pembulatan, dan semakin banyak perhitungan yang Anda lakukan terhadap angka bulat, semakin banyak Anda akan tertidur. Ini disebut gangguan katastropik . Beberapa aplikasi memerlukan ketepatan kritis, bahkan dengan mengorbankan beberapa kompleksitas terburuk. Untuk jenis aplikasi ini, algoritma yang mengoptimalkan perhitungannya untuk mengurangi atau menghilangkan gangguan katastropik telah dibuat.

Dengan demikian, merancang algoritma juga bisa menjadi trade-off antara abstraksi dan kendala.

Pada akhirnya, kita dapat mengatakan bahwa suatu algoritma adalah abstrak seperti targetnya, dan sebagai kebutuhan (arsitektur) prasyaratnya . Semakin spesifik target yang dituju oleh algoritma Anda, semakin besar kemungkinannya akan bergantung pada arsitektur perangkat keras.

Beberapa kata kunci terkait yang mungkin menarik bagi Anda:

• Lokalitas Referensi
• Optimasi putaran
• Optimasi sarang lingkaran
• Lokasi yang bisa diukur

Anda seharusnya tidak membingungkan suatu algoritma secara umum dengan algoritma matematika atau komputasi. Jika yang Anda maksud algoritma komputasi, ya, mereka tidak tergantung pada arsitektur mesin.

Definisi algoritma dari Wikipedia:

Dalam matematika dan ilmu komputer , suatu algoritma adalah serangkaian operasi selangkah demi selangkah yang harus dilakukan. Ada algoritma yang melakukan perhitungan , pemrosesan data , dan penalaran otomatis.

Definisi ini digunakan untuk merujuk beberapa tugas komputasi atau pemrosesan data tertutup. Dengan kata lain, perhitungan yang secara abstrak dapat dijalankan di Turing Machine . Namun, baru-baru ini ada konsep dalam matematika bernama komputasi Interaktif yang melibatkan komunikasi input / output dengan dunia eksternal selama perhitungan.

Dalam definisi umum, algoritma ini hanyalah resep (urutan instruksi). Saya pikir Anda tidak dapat memikirkan algoritma tanpa mengetahui set instruksi atau operasi yang dapat Anda gunakan; Operasi matematika adalah tentang perhitungan, lalu suatu algoritma yang mencakup langkah bernama ' memanaskan oven ' bukan algoritma matematika tetapi Anda dapat memberikannya kepada koki, karena dia tahu bagaimana cara menjalankannya.

Kemudian, Anda dapat membuat mesin yang dapat melakukan X, Y, Z .... masing-masing dapat digunakan dalam algoritma Anda sebagai instruksi. Tetapi jika mereka semua tentang komputasi tertutup (pada kenyataannya, perhitungan langkah kecil digital non-interaktif deterministik), maka orang dapat membuktikan bahwa mesin Anda setara dengan Turing Machine . Tetapi jika Anda menargetkan jenis komputasi lain (meneruskan nilai atau perhitungan interaktif [namun saya tidak yakin apakah mereka benar-benar jenis komputasi lain)) atau bahkan tidak ada tugas komputasi, Anda dapat memikirkan mesin yang dapat melakukan komputasi.

Pertanyaan dan jawaban ini juga menarik untuk mendapatkan perspektif yang lebih luas tentang algoritma.

Secara umum, algoritma dirancang untuk beberapa masalah tertentu sekaligus meminimalkan beberapa ukuran "biaya". Secara historis, banyak algoritma yang dirancang dengan asumsi bahwa biaya relatif dari operasi umum akan relatif sama pada banyak arsitektur, dan dengan demikian beberapa mesin khas akan menjalankan satu algoritma akan berjalan lebih baik daripada yang lain, maka pada kebanyakan mesin khas algoritma sebelumnya akan, pada terburuk, hanya sedikit lebih rendah dari yang terakhir. Seiring berlalunya waktu, anggapan seperti itu tidak berlaku seperti dulu.

Misalnya, dulu berapa kali suatu program perlu membaca sesuatu dari memori dianggap lebih penting daripada lokasi hal-hal yang harus dibaca. Membaca hal-hal yang letaknya berdekatan satu sama lain dalam ingatan agak lebih murah daripada membaca hal-hal yang berjauhan, tetapi tidak terlalu mencolok. Karena kecepatan main-CPU meningkat jauh melebihi kecepatan memori, pentingnya urutan akses telah meningkat secara signifikan. Ada kemungkinan untuk memiliki satu program menjalankan sepuluh kali lebih banyak instruksi daripada yang lain dan masih berjalan lebih cepat, jika 95% dari memori program sebelumnya menghasilkan hit cache L1 dan sebagian besar memori program yang terakhir mengambil kesalahan cache.

Selain itu, beberapa jenis algoritma yang terkait dengan konkurensi membuat berbagai asumsi tentang kapan data yang ditulis ke memori oleh satu inti prosesor akan "dilihat" oleh inti lainnya. Banyak prosesor memiliki berbagai cara sehingga mereka dapat membaca dan menulis memori, dengan biaya dan jaminan yang bervariasi tentang visibilitas. Beberapa algoritma akan bekerja dengan sangat baik pada arsitektur yang dapat memenuhi persyaratan visibilitas "gratis", tetapi buruk pada yang lain di mana instruksi yang diperlukan untuk jaminan tersebut mahal. Memang, pada beberapa arsitektur, algoritma terkait-konkurensi tertentu hanya dapat dijamin untuk bekerja dengan membatasi eksekusi pada inti CPU yang dibagi waktu saja (yang tentu saja akan mengalahkan titik menggunakan algoritma konkuren).

Banyak jawaban yang kehilangan fakta bahwa suatu algoritma dapat didefinisikan dalam istilah-istilah yang abstrak dari atau langsung, hubungan literal dengan suatu arsitektur. Algoritme harus tidak ambigu, tetapi masih ada ruang untuk lebih atau kurang spesifik.

Algoritma untuk mengonversi string menjadi all-caps dapat dengan mudah dijelaskan dalam pseudocode yang arsitektur-independen. Tetapi pada saat yang sama, tidak ada yang menghentikan Anda dari mendeskripsikan suatu algoritma untuk mengubah string menjadi huruf besar semua secara khusus pada arsitektur x86. Yang diperlukan hanyalah tugas pekerjaan rumah x86 Assembly. (Anda masih dapat melakukan ini dalam pseudocode - hanya pseudocode yang berkaitan dengan arsitektur itu!) Hanya fakta bahwa masalahnya secara khusus untuk melakukan ini pada arsitektur x86 tidak berarti Anda tidak lagi memiliki algoritma untuk menyelesaikannya.

Itu tergantung pada masalah yang didefinisikan algoritma untuk dipecahkan. Algoritme adalah arsitektur-independen jika masalahnya diselesaikan adalah arsitektur-independen (dan dengan asumsi bahwa ini tidak dibatalkan dengan cara algoritma dijelaskan atau disatukan). Masalahnya bisa berupa teori, papan tulis, atau bisa dalam hal arsitektur yang sangat spesifik. Dalam kasus terakhir, algoritma, pada gilirannya, akan terbatas pada bekerja dengan arsitektur itu.

Algoritma adalah urutan langkah-langkah. Mereka tidak bergantung pada apa yang (atau tidak) mengeksekusi mereka.

Namun, kompleksitas waktu suatu algoritma dapat bergantung pada apa yang mengeksekusinya. Itu sebabnya analisis terperinci dari suatu algoritma memerlukan "model perhitungan", seperti mesin akses acak .
Apakah atau tidak memori dapat diakses secara acak tentu mempengaruhi berapa lama algoritma Anda berjalan, dan sebagian besar algoritma menganggap ini adalah kasus sedangkan pada kenyataannya sebagian besar arsitektur tidak memenuhi kondisi ini.

Mereka berbeda pada konteks masalah yang berbeda. Algoritma adalah kumpulan langkah-langkah untuk menyelesaikan suatu masalah. Konteks masalah ini bisa secara teoritis apa saja. Oleh karena itu algoritma penyelesaian masalah dapat bergantung secara harfiah pada apa pun di alam semesta yang dapat kita bayangkan. Izinkan saya mengklarifikasi dengan sebuah contoh. Katakanlah Anda diberi tugas untuk,

Bangun algoritma yang akan mendistribusikan beban ke banyak inti saat multicore tersedia.

Sekarang bisakah Anda bayangkan algoritma Anda akan bergantung pada arsitektur atau tidak? Tentu saja ya .