Waktu akses disk ialah ketika disk drive beroperasi, disk berputar dengan kecepatan tetap.
Untuk dapat membaca dan menulis, head harus berada pada awal sector dari track yang diinginkan. Pemilihan track meliputi perpindahan head pada sistem movable head atau mekanisme elektronis pada head untuk sistem fixed head.
Karakteristik kinerja hard disk dibagi menjadi 3 bagian
1. SEEK TIME
Seek time adalah dimana drive berputar dan mencari/mengukur waktu yang dibutuhkan unit head pada lengan aktuator untuk melakukan perjalanan ke trek dari disk dan kemudian data akan dibaca atau ditulis.
Data pada media disimpan di sektor-sektor yang diatur dalam trek melingkar paralel (konsentris atau spiral tergantung pada jenis perangkat) dan ada aktuator dengan lengan yang menunda head yang dapat mentransfer data dengan media itu.
2. ROTATIONAL LATENCY
Rotational latency (kadang-kadang disebut delay rotasi atau hanya latency) adalah perlambatan menunggu rotasi disk untuk membawa sektor disk yang dibutuhkan di bawah HEAD READ - WRITE. Hal ini tergantung pada kecepatan rotasi dari sebuah disk (atau motor spindle ), diukur dalam revolusi per menit (RPM) . untuk drive magnetik berbasis media yang paling, rata-rata latency rotasi biasanya didasarkan pada hubungan empiris bahwa rata-rata latency dalam milidetik untuk seperti drive adalah setengah periode rotasi. Rotasi latency maksimum adalah waktu yang dibutuhkan untuk melakukan rotasi penuh tidak termasuk waktu spin-up (sebagai bagian yang relevan dari disk mungkin hanya melewati HEAD ketika permintaan tiba). Oleh karena itu. Latency rotasi dapat mengakibatkan waktu akses dapat ditingkatkan dengan meningkatkan kecepatan rotasi dari disk. ROTATIONAL LATENCY juga memiliki manfaat untuk meningkatkan throughput (dibahas nanti dalam artikel ini).
Untuk rincian lebih lanjut tentang tata letak lagu melihat penyimpanan Disk.
Kecepatan motor spindle dapat menggunakan salah satu dari dua jenis metode rotasi disk: 1) kecepatan linear konstan (CLV), digunakan terutama dalam penyimpanan optik, bervariasi kecepatan rotasi dari disk optik tergantung pada posisi kepala, dan 2) konstan kecepatan sudut (CAV), yang digunakan dalam HDD, FDD standar, sistem cakram optik beberapa, dan catatan vinil audio, media berputar pada satu kecepatan konstan terlepas dari mana kepala diposisikan.
3. ACCESS TIME
ACCESS TIME adalah ukuran waktu yang diperlukan sebelum drive benar-benar dapat mentransfer data. Faktor-faktor yang mengontrol waktu ini pada drive berputar sebagian besar terkait dengan sifat mekanik dari kepala berputar disk dan bergerak.
metode ini terdiri dari beberapa elemen dapat diukur secara independen yang ditambahkan bersama-sama untuk mendapatkan nilai tunggal ketika mengevaluasi kinerja perangkat penyimpanan. Waktu akses dapat bervariasi secara signifikan, sehingga biasanya disediakan oleh produsen atau diukur dalam tolok ukur sebagai rata-rata .
Selasa, 20 Desember 2011
Akses Cache Memory
Organisasi Cache
Cache Asosiatif
Disebut juga Fully Associative Cache.
- Menyimpan tagnya di dalam memori asosiatif atau memori yang ekuivalen secara fungsional.
- Cache dapat menempatkan sembarang jalur refill selama akses memori.
- Membandingkan alamat yang ada dengan semua alamat yang disimpan.
Dalam rancangan cache asosiatif-penuh :(detail)
• Suatu blok data dapat ditempatkan pada baris cache manapun.
• Alamat dibagi menjadi dua bagian yakni bit rendah dan bit tinggi.
• Bit rendah membentuk offset di dalam baris cache, sedangkan bit tinggi membentuk tag untuk dicocokkan dengan rujukan.
• Cache asosiatif-penuh harus punya mekanisme untuk menentukan ke dalam baris mana blok ditempatkan.
• Blok dapat ditempatkan dalam baris manapun yang kosong. Bila semua baris cache penuh harus ditentukan blok mana yang dikeluarkan dari cache.
• Digunakan prinsip LRU (least recently used) yakni blok yang paling lama tidak dipakai dikeluarkan dari cache.
• Cukup mahal mengimplementasikannya.
• Resiko : memperbanyak implementasi rangkaian hardware untuk membandingkan tag thadap semua baris cache.
Direct Mapped Cache (Cache yang dipetakan langsung)
Membagi memory utama menjadi K kolom dengan N refill line per kolomnya.
Operasi Pembacaan Cache secara Direct :
- memetakan masing-masing blok memori utama hanya ke sebuah saluran cache saja.
- Fungsi pemetaan mudah diimplementasikan dengan menggunakan alamat.
- Untuk mengakses cache, setiap alamat memori utama dianggap terdiri dari tiga field.
Organisasi cache yang dipetakan langsung : (detail)
• menyimpan satu tag perbaris dalam larik tag-nya
• Selama pengaksesan memori, cache menggunakan bit-bit tengah alamat sebagai indeks ke larik tagnya.
• Tag dicocokkan dengan 16-bit teratas dari alamat memori yang diakses.
• Jika cocok, data yang ditunjukan oleh nilai offset akan dikirim ke prosesor. Bila tidak cocok, isi baris cache diganti dengan blok yang diperlukan, dari memori utama.
• Hanya memerlukan satu kali pembandingan untuk setiap akses ke cache.
• Cocok untuk sistem komputer yang memerlukan frekuensi detak tinggi
Set Cache Asosiatif
-Mengkombinasikan organisasi asosiatif dan direct (langsung).
- Mengorganisir memori utama dan memorinya sendiri menjadi kolom jalur refil N.
- Cache dibagi menjadi beberapa set/himpunan
- Setiap himpunan terdiri dr sejumlah jalur
- Sebuah blok yang diberikan memetakan ke jalur manapun dalam himpunan yang diberikan
(Misal Block B dapat berada di jalur manapundalam himpuan i)
- Misal 2 jalur per himpunan
2 cara pemetaan asosiatif
- Sebuah blok yang diberikan dapat pada salah satu dari 2 jalur dalam sebuah himpunan saja
Sector Mapped Cache (Cache yang dipetakan sector)
- Merupakan modifikasi dari cache asosiatif.
-Jalur refill memori utama dan cache dikelompokan menjadi sector yang disebut row(baris).
Dalam mendesain sistem cache, yang pertama kali perlu diperhatikan adalah masalah penempatan suatu blok data/instruksi dari memori utama ke baris-baris cache. Berkaitan dengan masalah itu, ada tiga macam organisasi cache yakni organisasi cache yang dipetakan langsung (direct-mapped), asosiatif penuh (fully associative), dan asosiatif-kelompok ( set-associative).
Cache Asosiatif
Disebut juga Fully Associative Cache.
- Menyimpan tagnya di dalam memori asosiatif atau memori yang ekuivalen secara fungsional.
- Cache dapat menempatkan sembarang jalur refill selama akses memori.
- Membandingkan alamat yang ada dengan semua alamat yang disimpan.
Dalam rancangan cache asosiatif-penuh :(detail)
• Suatu blok data dapat ditempatkan pada baris cache manapun.
• Alamat dibagi menjadi dua bagian yakni bit rendah dan bit tinggi.
• Bit rendah membentuk offset di dalam baris cache, sedangkan bit tinggi membentuk tag untuk dicocokkan dengan rujukan.
• Cache asosiatif-penuh harus punya mekanisme untuk menentukan ke dalam baris mana blok ditempatkan.
• Blok dapat ditempatkan dalam baris manapun yang kosong. Bila semua baris cache penuh harus ditentukan blok mana yang dikeluarkan dari cache.
• Digunakan prinsip LRU (least recently used) yakni blok yang paling lama tidak dipakai dikeluarkan dari cache.
• Cukup mahal mengimplementasikannya.
• Resiko : memperbanyak implementasi rangkaian hardware untuk membandingkan tag thadap semua baris cache.
Direct Mapped Cache (Cache yang dipetakan langsung)
Membagi memory utama menjadi K kolom dengan N refill line per kolomnya.
Operasi Pembacaan Cache secara Direct :
- memetakan masing-masing blok memori utama hanya ke sebuah saluran cache saja.
- Fungsi pemetaan mudah diimplementasikan dengan menggunakan alamat.
- Untuk mengakses cache, setiap alamat memori utama dianggap terdiri dari tiga field.
Organisasi cache yang dipetakan langsung : (detail)
• menyimpan satu tag perbaris dalam larik tag-nya
• Selama pengaksesan memori, cache menggunakan bit-bit tengah alamat sebagai indeks ke larik tagnya.
• Tag dicocokkan dengan 16-bit teratas dari alamat memori yang diakses.
• Jika cocok, data yang ditunjukan oleh nilai offset akan dikirim ke prosesor. Bila tidak cocok, isi baris cache diganti dengan blok yang diperlukan, dari memori utama.
• Hanya memerlukan satu kali pembandingan untuk setiap akses ke cache.
• Cocok untuk sistem komputer yang memerlukan frekuensi detak tinggi
Set Cache Asosiatif
-Mengkombinasikan organisasi asosiatif dan direct (langsung).
- Mengorganisir memori utama dan memorinya sendiri menjadi kolom jalur refil N.
- Cache dibagi menjadi beberapa set/himpunan
- Setiap himpunan terdiri dr sejumlah jalur
- Sebuah blok yang diberikan memetakan ke jalur manapun dalam himpunan yang diberikan
(Misal Block B dapat berada di jalur manapundalam himpuan i)
- Misal 2 jalur per himpunan
2 cara pemetaan asosiatif
- Sebuah blok yang diberikan dapat pada salah satu dari 2 jalur dalam sebuah himpunan saja
Sector Mapped Cache (Cache yang dipetakan sector)
- Merupakan modifikasi dari cache asosiatif.
-Jalur refill memori utama dan cache dikelompokan menjadi sector yang disebut row(baris).
Rabu, 28 September 2011
Kisah Lucu Penuh Motivasi Dan Inspirasi
1. Setelah makan malam, seorang ibu dan putrinya bersama-sama mencuci mangkuk dan piring, sedangkan ayah dan putranya menonton TV di ruang tamu. Mendadak, dari arah dapur terdengar suara piring yang pecah, kemudian sunyi senyap. Si putra memandang ke arah ayahnya dan berkata, “Pasti ibu yang memecahkan piring itu.” “Bagaimana kamu tahu?” kata si Ayah. “Karena tak terdengar suara dia memarahi orang lain,” sahut anaknya.
2. Ada dua grup pariwisata yang pergi bertamasya ke pulau Yi Do di Jepang. Kondisi jalannya sangat buruk, sepanjang jalan terdapat banyak lubang. Salah satu pemandu berulang-ulang mengatakan keadaan jalannya rusak parah dan tak terawat. Sedangkan pemandu yang satunya lagi berbicara kepada para turisnya dengan nada puitis, “Yang kita lalui sekarang ini adalah jalan protokol ternama di Yi Do yang bernama jalan berdekik yang mempesona.”
3. Murid kelas 3 SD yang sama, mereka memiliki cita-cita yang sama pula yaitu menjadi badut. Guru dari Tiongkok pasti mencela, “Tidak mempunyai cita-cita yang luhur, anak yang tidak bisa dibina!” Sedangkan guru dari Barat akan bilang, “Semoga Anda membawakan kecerian bagi seluruh dunia!”
4. Istri sedang memasak di dapur. Suami yang berada di sampingnya mengoceh tak berkesudahan, “Pelan sedikit, hati-hati! Apinya terlalu besar. Ikannya cepat dibalik, minyaknya terlalu banyak!” Istrinya secara spontan menjawab, “Saya mengerti bagaimana cara memasak sayur.” Suaminya dengan tenang menjawab, “Saya hanya ingin dirimu mengerti bagaimana perasaan saya … saat saya sedang mengemudikan mobil, engkau yang berada disamping mengoceh tak ada hentinya.”
5. Sebuah bus yang penuh dengan muatan penumpang sedang melaju dengan cepat menelusuri jalanan yang menurun, ada seseorang yang mengejar bus ini dari belakang. Seorang penumpang mengeluarkan kepala keluar jendala bus dan berkata dengan orang yang mengejar bus, “Hai kawan! Sudahlah Anda tak mungkin bisa mengejar!” Orang tersebut menjawab, “Saya harus mengejarnya . . .” Dengan nafas tersenggal-senggal dia berkata, “Saya adalah pengemudi dari bus ini!”
6. Si A : “Tetangga yang yang baru pindah itu sungguh jahat, kemarin tengah malam dia datang ke rumah saya dan terus menerus menekan bel di rumah saya.”
Si B : “Memang sungguh jahat! Adakah Anda segera melapor polisi?”
Si A : “Tidak. Saya menganggap mereka orang gila, yang terus menerus meniup terompet kecil saya.”
7. Zhang San sedang mengemudikan mobil berjalan di jalan pegunungan, ketika dengan santai menikmati pemandangan yang indah, mendadak dari arah depan datang sebuah truk barang. Si sopir truk membuka jendela dan berteriak dengan keras, “Babi!” Mendengar suara ini Zhang San menjadi emosi, dia juga membuka jendela memaki, “Kamu sendiri yang babi!” Baru saja selesai memaki, dia telah bertabrakan dengan gerombolan babi yang sedang menyeberangi jalan.
Quote:
| Kita semua sudah terbiasa menggunakan standar yang berbeda melihat orang lain dan memandang diri sendiri, sehingga acapkali kita menuntut orang lain dengan serius, tetapi memperlakukan diri sendiri dengan penuh toleran. |
Quote:
| Walaupun keadaannya sama, namun pikiran yang berbeda akan menimbulkan sikap yang berbeda pula. Pikiran adalah suatu hal yang sangat menakjubkan, bagaimana berpikir, keputusan berada di tangan Anda. |
Quote:
| Terkadang orang yang lebih tua, bukan hanya lebih banyak menuntut daripada memberi semangat, malahan sering membatasi definisi keberhasilan dengan arti yang sempit. |
Quote:
| Belajar memberi kelonggaran kepada orang lain itu tidak sulit, asalkan Anda mau dengan serius berdiri di sudut dan pandangan orang lain melihat suatu masalah. |
Quote:
| Ada sebagian orang harus berusaha keras dengan sangat serius, jika tidak demikian, maka akibatnya akan sangat tragis! Dan juga dikarenakan harus menghadapi dengan sekuat tenaga, maka kemampuan yang masih terpendam dan sifat-sifat khusus yang tidak diketahui oleh orang lain selama ini akan sepenuhnya muncul keluar. |
Si B : “Memang sungguh jahat! Adakah Anda segera melapor polisi?”
Si A : “Tidak. Saya menganggap mereka orang gila, yang terus menerus meniup terompet kecil saya.”
Quote:
| Semua kejadian pasti ada sebabnya, jika sebelumnya kita bisa melihat kekurangan kita sendiri, maka jawabannya pasti berbeda. |
Quote:
Jangan salah tafsir maksud kebaikan dari orang lain, hal tersebut akan menyebabkan kerugian Anda, juga membuat orang lain terhina. sumber : http://forum.vivanews.com/aneh-dan-lucu/200551-7-kisah-lucu-penuh-motivasi-dan-inspirasi.html
Konsep-Konsep Laptop Masa Depan Terunik dan Keren
Diperuntukkan bagi penggunaan didalam mobil khususnya yang berdedikasi bertugas di dalam mobil. hampir gak masuk akal memang tapi laptop yang satu ini sangat ringan dengan keyboard layar sentuh ditambah dengan tampilannya yang transparan
HP Laptop concept
Laptop ini rancangan HP dimana keseluruhan desainnya lebih meyakinkan.
V12
Merupakan hasil rancangan Canova dimana sudah menggunakan dual layar yang dilengkapi dengan 2 layar tampilan. Yang satu ini cocok banget bagi Editor Grafis.
CEATEC - DJ laptop
Hasil rancangan Fujitsu dimana terdapat keypad sentuh dengan layar backlight dengan dilengkapi 5.1 surround sound system beserta tombol musik. Tak salah jika Laptop 20 inci ini dijuluki Laptop DJ.
Flexi PDA Concept Laptop
Kelebihannya yang bikin memukau adalah Layarnya yang fleksibel plus 100% tahan air.
Frog Design laptop
Sebutannya Gelfrog yang mana ringannya hampir seringan koran. Bayangkan pula polanya yang gak nahan.
Frog Design laptop
Laptop ini buatan Fujitsu dengan tipe tampilan kertas yang fleksibel, super ringan bahkan tampak bagaikan folder kantor.
Itel Ziba Design Concept laptop
Laptop ini bobotnya hanya 2.25 tapi dengan layar 17.7 inci.
Compenion prototype
Layar sentunnya saja sudah OLED dan berdisain slinder. Plus mendukung multi layar sentuh.
Vaio Zoo
Merupakan konsep notebook hologram dimana 101% transparan, sangat tipis dan bentuknya bikin mupeng.
Speculative Execution
Gagasan Utama
Eksekusi spekulatif adalah optimasi kinerja. Ide utama adalah untuk melakukan pekerjaan yang mungkin tidak diperlukan. Targetnya adalah untuk menyediakan konkurensi lebih jika sumber daya tambahan yang tersedia. Teknologi berikut menggunakan ide ini:
Prefetching dalam memori dan sistem file
Cabang prediksi
Kontrol konkurensi Optimis dalam sistem database
Prosesor
Pipelined mikroprosesor modern menggunakan eksekusi spekulatif untuk mengurangi biaya instruksi cabang bersyarat menggunakan skema yang memprediksi jalur eksekusi dari suatu program berdasarkan sejarah eksekusi cabang. Ternyata bahwa dalam rangka meningkatkan kinerja dan pemanfaatan sumber daya komputer, beberapa instruksi harus dijadwalkan terlebih dahulu di tempat yang tidak ditentukan bahwa instruksi tersebut harus dieksekusi sama sekali, di depan cabang.
Compiler
Dalam optimasi compiler untuk sistem multiprocessing, eksekusi spekulatif melibatkan prosesor menganggur mengeksekusi kode di blok prosesor berikutnya, dalam hal tidak ada ketergantungan pada kode yang dapat berjalan pada prosesor lainnya. Keuntungan dari skema ini adalah mengurangi waktu respon untuk prosesor individu dan sistem secara keseluruhan. Namun, ada hukuman bersih untuk kasus rata-rata, karena dalam kasus taruhan yang buruk, pipa harus memerah. Compiler terbatas dalam mengeluarkan instruksi eksekusi spekulatif, karena memerlukan bantuan perangkat keras untuk buffer efek spekulasi-instruksi dieksekusi. Tanpa dukungan hardware, compiler hanya bisa mengeluarkan instruksi spekulatif yang memiliki efek samping dalam hal spekulasi yang salah.
Eksekusi Bersemangat
Eksekusi bersemangat adalah bentuk eksekusi spekulatif di mana kedua sisi cabang kondisional dijalankan, namun hasil berkomitmen hanya jika predikat benar. Dengan sumber daya terbatas, eksekusi bersemangat (juga dikenal sebagai eksekusi oracle) akan dalam teori memberikan kinerja yang sama seperti prediksi cabang yang sempurna. Dengan sumber daya yang terbatas ingin eksekusi harus digunakan hati-hati karena jumlah sumber daya yang dibutuhkan tumbuh secara eksponensial dengan masing-masing tingkat cabang dieksekusi bersemangat .
Evaluasi Malas
Malas evaluasi tidak berspekulasi. Penggabungan eksekusi spekulatif dalam implementasi dari bahasa pemrograman Haskell merupakan topik penelitian saat ini. Haskell bersemangat dirancang di sekitar gagasan eksekusi spekulatif. Versi terbaru dukungan GHC jenis eksekusi spekulatif dengan mekanisme aborsi untuk kembali dalam kasus pilihan yang buruk disebut eksekusi optimis .
Eksekusi spekulatif adalah optimasi kinerja. Ide utama adalah untuk melakukan pekerjaan yang mungkin tidak diperlukan. Targetnya adalah untuk menyediakan konkurensi lebih jika sumber daya tambahan yang tersedia. Teknologi berikut menggunakan ide ini:
Prefetching dalam memori dan sistem file
Cabang prediksi
Kontrol konkurensi Optimis dalam sistem database
Prosesor
Pipelined mikroprosesor modern menggunakan eksekusi spekulatif untuk mengurangi biaya instruksi cabang bersyarat menggunakan skema yang memprediksi jalur eksekusi dari suatu program berdasarkan sejarah eksekusi cabang. Ternyata bahwa dalam rangka meningkatkan kinerja dan pemanfaatan sumber daya komputer, beberapa instruksi harus dijadwalkan terlebih dahulu di tempat yang tidak ditentukan bahwa instruksi tersebut harus dieksekusi sama sekali, di depan cabang.
Compiler
Dalam optimasi compiler untuk sistem multiprocessing, eksekusi spekulatif melibatkan prosesor menganggur mengeksekusi kode di blok prosesor berikutnya, dalam hal tidak ada ketergantungan pada kode yang dapat berjalan pada prosesor lainnya. Keuntungan dari skema ini adalah mengurangi waktu respon untuk prosesor individu dan sistem secara keseluruhan. Namun, ada hukuman bersih untuk kasus rata-rata, karena dalam kasus taruhan yang buruk, pipa harus memerah. Compiler terbatas dalam mengeluarkan instruksi eksekusi spekulatif, karena memerlukan bantuan perangkat keras untuk buffer efek spekulasi-instruksi dieksekusi. Tanpa dukungan hardware, compiler hanya bisa mengeluarkan instruksi spekulatif yang memiliki efek samping dalam hal spekulasi yang salah.
Eksekusi Bersemangat
Eksekusi bersemangat adalah bentuk eksekusi spekulatif di mana kedua sisi cabang kondisional dijalankan, namun hasil berkomitmen hanya jika predikat benar. Dengan sumber daya terbatas, eksekusi bersemangat (juga dikenal sebagai eksekusi oracle) akan dalam teori memberikan kinerja yang sama seperti prediksi cabang yang sempurna. Dengan sumber daya yang terbatas ingin eksekusi harus digunakan hati-hati karena jumlah sumber daya yang dibutuhkan tumbuh secara eksponensial dengan masing-masing tingkat cabang dieksekusi bersemangat .
Evaluasi Malas
Malas evaluasi tidak berspekulasi. Penggabungan eksekusi spekulatif dalam implementasi dari bahasa pemrograman Haskell merupakan topik penelitian saat ini. Haskell bersemangat dirancang di sekitar gagasan eksekusi spekulatif. Versi terbaru dukungan GHC jenis eksekusi spekulatif dengan mekanisme aborsi untuk kembali dalam kasus pilihan yang buruk disebut eksekusi optimis .
Data Flow Analysis
Prinsip-prinsip dasar
Ini adalah proses pengumpulan informasi tentang cara variabel yang digunakan, didefinisikan dalam program ini. Analisis aliran data upaya untuk memperoleh informasi tertentu pada setiap titik dalam prosedur. Biasanya, itu sudah cukup untuk memperoleh informasi ini pada batas blok dasar, sejak dari bahwa adalah mudah untuk menghitung informasi pada poin di blok dasar. Dalam analisis arus maju, negara keluar dari blok adalah fungsi negara masuk blok. Fungsi ini adalah komposisi efek dari pernyataan di blok. Keadaan masuknya blok adalah fungsi dari negara-negara keluar dari pendahulunya. Ini menghasilkan satu set data-aliran persamaan:
Untuk setiap blok b:
outb = transb (inb)
in_b = join_ {p \ di pred_b} (out_p)
Dalam hal ini, transb adalah fungsi transfer blok b. Ia bekerja pada negara inb masuk, yang menghasilkan outb negara keluar. Operasi bergabung bergabung menggabungkan menyatakan keluar dari pendahulu p \ di pred_b b, menghasilkan negara masuknya b.
Setelah menyelesaikan set persamaan, negara masuk dan / atau keluar dari blok dapat digunakan untuk mendapatkan properti dari program pada batas blok. Fungsi transfer setiap pernyataan secara terpisah dapat diterapkan untuk mendapatkan informasi pada suatu titik di dalam blok dasar.
Setiap jenis tertentu dari data-aliran analisis telah mentransfer sendiri fungsi dan bergabung dengan operasi. Beberapa data-aliran masalah, analisis arus mundur. Ini mengikuti rencana yang sama, kecuali bahwa fungsi transfer diterapkan kepada negara keluar menghasilkan negara masuk, dan operasi bergabung bekerja pada masuknya negara penerus untuk menghasilkan negara keluar.
Titik masuk (aliran ke depan) memainkan peran penting: Karena tidak memiliki pendahulu, masuknya negara didefinisikan dengan baik pada awal analisis. Misalnya, himpunan variabel lokal dengan nilai-nilai diketahui kosong. Jika grafik aliran kontrol tidak mengandung siklus (tidak ada loop eksplisit atau implisit dalam prosedur) memecahkan persamaan secara langsung. Grafik aliran kontrol kemudian dapat topologi diurutkan, berjalan dalam urutan seperti ini, negara-negara entri dapat dihitung pada awal setiap blok, karena semua pendahulu dari blok yang telah diproses, sehingga mereka menyatakan keluar tersedia. Jika grafik aliran kontrol tidak mengandung siklus, sebuah algoritma yang lebih canggih diperlukan.[Sunting] Sebuah algoritma iteratif
Cara yang paling umum untuk memecahkan persamaan aliran data adalah dengan menggunakan algoritma iteratif. Ini dimulai dengan perkiraan negara di-blok masing-masing. Out-negara tersebut kemudian dihitung dengan menerapkan fungsi transfer pada di negara-negara. Dari ini, di-negara yang diperbarui dengan menerapkan operasi bergabung. Dua terakhir langkah ini diulang sampai kita mencapai fixpoint disebut: situasi di mana di negara-negara (dan keluar-negara bagian di konsekuensi) tidak berubah.
Sebuah algoritma dasar untuk memecahkan persamaan aliran data adalah round-robin algoritma iteratif:
untuk i ← 1 sampai N
menginisialisasi node i
sementara (set masih berubah)
untuk i ← 1 sampai N
recompute set pada node i
[Sunting] Konvergensi
Untuk digunakan, pendekatan iteratif harus benar-benar mencapai suatu fixpoint. Hal ini dapat dijamin oleh memaksakan kendala pada kombinasi dari domain nilai negara, fungsi transfer dan operasi join.
Nilai domain harus urutan parsial dengan ketinggian yang terbatas (yaitu, tidak ada rantai ascending terbatas x1 <x2 <...). Kombinasi dari fungsi transfer dan operasi harus bergabung monoton sehubungan dengan urutan parsial. Kemonotonan memastikan bahwa pada setiap iterasi nilai baik akan tetap sama atau akan tumbuh lebih besar, sementara tingginya terbatas memastikan bahwa hal itu tidak bisa tumbuh tanpa batas. Dengan demikian kita akhirnya akan mencapai situasi di mana T (x) = x untuk semua x, yang fixpoint tersebut.[Sunting] Pendekatan daftar pekerjaan
Sangat mudah untuk memperbaiki algoritma di atas dengan memperhatikan bahwa di negara-blok tidak akan berubah jika keluar-negara pendahulunya tidak berubah. Oleh karena itu, kami memperkenalkan sebuah daftar kerja: daftar blok yang masih harus diproses. Setiap kali keluar-negara perubahan blok, kita menambahkan penerus ke daftar kerja. Dalam setiap iterasi, blok dihapus dari daftar pekerjaan. Its keluar-negara dihitung. Jika out-negara berubah, penerus blok tersebut ditambahkan ke daftar kerja. Untuk efisiensi, blok tidak boleh dalam daftar bekerja lebih dari sekali.
Algoritma ini dimulai dengan menempatkan titik masuk dalam daftar pekerjaan. Ini berakhir ketika daftar pekerjaan kosong.[Sunting] Perintah penting
Efisiensi iteratif memecahkan persamaan aliran data dipengaruhi oleh urutan di mana node lokal dikunjungi. Selain itu, tergantung, apakah data-aliran persamaan yang digunakan untuk maju atau mundur aliran data analisis atas CFG tersebut. Intuitif, dalam masalah aliran ke depan, akan tercepat jika semua pendahulu dari blok telah diproses sebelum blok itu sendiri, sejak saat iterasi akan menggunakan informasi terbaru. Dengan tidak adanya loop adalah mungkin untuk memesan blok sedemikian rupa sehingga benar keluar-negara dihitung dengan memproses setiap blok hanya sekali.
Dalam berikut, pesanan beberapa iterasi untuk menyelesaikan persamaan aliran data yang dibahas (sebuah konsep yang berhubungan untuk memesan iterasi dari CFG adalah pohon traversal dari pohon).
Urutan acak - Ini pesanan iterasi tidak menyadari apakah data-aliran persamaan memecahkan masalah data aliran maju atau mundur. Oleh karena itu, kinerja yang relatif miskin dibandingkan dengan perintah iterasi khusus.
Postorder - Ini adalah perintah iterasi khas untuk mundur data masalah arus. Dalam iterasi postorder, node dikunjungi setelah semua node penggantinya telah dikunjungi. Biasanya, iterasi postorder diimplementasikan dengan strategi depth-first.
Sebaliknya postorder - Ini adalah perintah iterasi khas untuk meneruskan data-masalah arus. Dalam reverse-postorder iterasi, node dikunjungi sebelum semua node penggantinya telah dikunjungi, kecuali bila penggantinya adalah dicapai oleh ujung belakang. (Catatan bahwa ini tidak sama dengan preorder.)
[Sunting] Inisialisasi
Nilai awal di-negara adalah penting untuk mendapatkan hasil yang benar dan akurat. Jika hasilnya digunakan untuk optimasi compiler, mereka harus memberikan informasi yang konservatif, yaitu ketika menerapkan informasi, program tidak harus mengubah semantik. Iterasi dari algoritma fixpoint akan mengambil nilai-nilai dalam arah elemen maksimum. Menginisialisasi semua blok dengan elemen maksimum karena itu tidak berguna. Setidaknya satu blok dimulai di negara dengan nilai kurang maksimal. Rincian tergantung pada masalah data-aliran. Jika elemen minimal merupakan informasi benar-benar konservatif, hasilnya dapat digunakan dengan aman bahkan selama iterasi data aliran. Jika itu merupakan informasi yang paling akurat, fixpoint harus dicapai sebelum hasil dapat diterapkan.[Sunting] Contoh
Berikut ini adalah contoh dari sifat-sifat dari program komputer yang dapat dihitung dengan data-aliran analisis. Perhatikan bahwa sifat dihitung dengan analisis aliran data biasanya hanya perkiraan sifat nyata. Hal ini karena data-flow analisis beroperasi pada struktur sintaksis CFG tanpa simulasi aliran kontrol yang tepat dari program. Namun, untuk menjadi masih berguna dalam praktek, algoritma analisis data flow biasanya dirancang untuk menghitung masing-masing pendekatan bawah atas sifat program nyata.[Sunting] Analisis Teruskan
Analisis Definisi mencapai menghitung untuk setiap titik program set definisi yang berpotensi dapat mencapai titik ini program.
1: jika b == 4 maka2: a = 5;3: lain4: a = 3;5: endif6:7: jika <4 maka8: ...
Definisi mencapai variabel "a" pada baris 7 adalah himpunan tugas a = 5 pada baris 2 dan a = 3 pada baris 4.[Sunting] Analisis Mundur
Analisis variabel tinggal menghitung untuk setiap titik program variabel yang mungkin berpotensi dibaca kemudian sebelum update menulis berikutnya. Hasilnya adalah biasanya digunakan oleh eliminasi kode mati untuk menghapus pernyataan yang menetapkan ke suatu variabel yang nilainya tidak digunakan sesudahnya.
Di-negara blok adalah himpunan variabel yang tinggal di ujung blok. Its luar negara adalah serangkaian variabel yang ada tinggal pada awal itu. Di-negara adalah gabungan dari out-negara dari blok penerus. Fungsi transfer dari sebuah pernyataan diterapkan dengan membuat variabel yang ditulis mati, kemudian membuat variabel yang dibaca hidup.
/ / Keluar: {}b1: a = 3;
b = 5;
d = 4;
jika a> b maka
/ / Dalam: {a, b, d}
/ / Keluar: {a, b}b2: c = a + b;
d = 2;
/ / Dalam: {b, d}
/ / Keluar: {b, d}b3: endif
c = 4;
kembali b * d + c;
/ / Dalam: {}
Out-negara b3 hanya berisi b dan d, karena c telah ditulis. Di negara-b1 adalah gabungan dari out-negara bagian b2 dan b3. Definisi c dalam b2 dapat dihapus, karena c adalah tidak hidup segera setelah pernyataan itu.
Memecahkan persamaan aliran data dimulai dengan menginisialisasi semua di-negara-negara dan keluar ke set kosong. Daftar kerja diinisialisasi dengan memasukkan titik keluar (B3) dalam daftar pekerjaan (khas untuk mengalir ke belakang). Dihitung nya keluar-negara berbeda dari yang sebelumnya, sehingga pendahulunya b1 dan b2 dimasukkan dan proses berlanjut. Kemajuan tersebut diringkas dalam tabel di bawah ini.pengolahan di negara-negara lama keluar baru keluar-negara daftar pekerjaanb3 {} {} {b, d} (b1, b2)b1 {b, d} {} {} (b2)b2 {b, d} {} {a, b} (b1)b1 {a, b, d} {} {} ()
Catatan b1 yang masuk dalam daftar sebelum b2, b1 pengolahan yang memaksa dua kali (b1 adalah kembali dimasukkan sebagai pendahulu dari b2). Memasukkan b1 b2 sebelumnya akan membiarkan selesai sebelumnya.
Menginisialisasi dengan himpunan kosong adalah inisialisasi optimis: semua variabel dimulai sebagai mati. Perhatikan bahwa keluar-negara tidak dapat menyusut dari satu iterasi ke depan, meskipun keluar-negara dapat lebih kecil yang di-negara. Hal ini dapat dilihat dari fakta bahwa setelah iterasi pertama keluar-satunya negara dapat berubah dengan perubahan negara dalam-. Karena di negara dimulai sebagai himpunan kosong, hanya dapat tumbuh di iterasi lebih lanjut.[Sunting] Pendekatan-pendekatan lain
Pada tahun 2002, Markus Mohnen dijelaskan metode baru data-flow analisis yang tidak memerlukan konstruksi eksplisit dari sebuah grafik aliran data, [2], bukan mengandalkan pada interpretasi abstrak program dan menjaga working set counter program. Pada setiap cabang kondisional, baik target ditambahkan ke working set. Masing-masing jalan diikuti untuk sebagai petunjuk sebanyak mungkin (sampai akhir program atau sampai telah dilingkarkan dengan tidak ada perubahan), dan kemudian dihapus dari set dan program counter berikutnya diambil.[Sunting] Bit masalah vektor
Contoh di atas adalah masalah di mana nilai data-aliran set, misalnya set definisi mencapai (Menggunakan sedikit untuk posisi definisi dalam program), atau set variabel hidup. Set ini dapat direpresentasikan secara efisien sebagai vektor bit, di mana setiap bit mewakili keanggotaan set satu elemen tertentu. Menggunakan representasi ini, fungsi bergabung dan transfer dapat diimplementasikan sebagai operasi bitwise logis. Operasi bergabung biasanya serikat buruh atau persimpangan, dilaksanakan oleh bitwise logis atau dan logis dan. Fungsi transfer untuk setiap blok dapat diuraikan dalam apa yang disebut gen dan membunuh set.
Sebagai contoh, dalam hidup-variabel analisis, operasi bergabung adalah serikat. Set membunuh adalah himpunan variabel yang ditulis dalam blok, sedangkan set gen adalah himpunan variabel yang dibaca tanpa tertulis pertama. Data-aliran persamaan menjadi
out_b = \ bigcup_ {s \ di succ_b} in_s
in_b = (out_b - kill_b) \ cangkir gen_b
Dalam operasi logis, ini berbunyi sebagai
keluar (b) = 0
untuk s di succ (b)
keluar (b) = keluar (b) atau (s)
dalam (b) = (keluar (b) dan tidak membunuh (b)) atau gen (b)
[Sunting] Sensitivitas
Analisis aliran data secara inheren aliran-sensitif. Analisis aliran data biasanya jalan-insensitive, meskipun mungkin untuk mendefinisikan data flow persamaan yang menghasilkan jalur-sensitif analisis.
Aliran-sensitif analisis memperhitungkan urutan pernyataan dalam program. Sebagai contoh, aliran-insensitive analisis alias pointer dapat menentukan "variabel x dan y dapat merujuk ke lokasi yang sama", sementara analisis aliran-sensitif dapat menentukan "setelah pernyataan 20, variabel x dan y dapat merujuk ke lokasi yang sama".
Sebuah jalur-sensitif analisis menghitung potongan informasi yang berbeda tergantung pada analisis predikat di instruksi cabang bersyarat. Sebagai contoh, jika cabang berisi kondisi x> 0, maka pada musim gugur-melalui jalan setapak, analisis akan berasumsi bahwa x <= 0 dan pada target cabang itu akan berasumsi bahwa memang x> 0 berlaku.
Sebuah konteks-sensitif analisis adalah analisis interprosedural yang mempertimbangkan konteks menelepon ketika menganalisis target dari pemanggilan fungsi. Secara khusus, menggunakan informasi konteks yang dapat melompat kembali ke situs panggilan asli, sedangkan tanpa informasi itu, analisis informasi harus disebarkan kembali ke semua situs panggilan mungkin, berpotensi kehilangan presisi.
Ini adalah proses pengumpulan informasi tentang cara variabel yang digunakan, didefinisikan dalam program ini. Analisis aliran data upaya untuk memperoleh informasi tertentu pada setiap titik dalam prosedur. Biasanya, itu sudah cukup untuk memperoleh informasi ini pada batas blok dasar, sejak dari bahwa adalah mudah untuk menghitung informasi pada poin di blok dasar. Dalam analisis arus maju, negara keluar dari blok adalah fungsi negara masuk blok. Fungsi ini adalah komposisi efek dari pernyataan di blok. Keadaan masuknya blok adalah fungsi dari negara-negara keluar dari pendahulunya. Ini menghasilkan satu set data-aliran persamaan:
Untuk setiap blok b:
outb = transb (inb)
in_b = join_ {p \ di pred_b} (out_p)
Dalam hal ini, transb adalah fungsi transfer blok b. Ia bekerja pada negara inb masuk, yang menghasilkan outb negara keluar. Operasi bergabung bergabung menggabungkan menyatakan keluar dari pendahulu p \ di pred_b b, menghasilkan negara masuknya b.
Setelah menyelesaikan set persamaan, negara masuk dan / atau keluar dari blok dapat digunakan untuk mendapatkan properti dari program pada batas blok. Fungsi transfer setiap pernyataan secara terpisah dapat diterapkan untuk mendapatkan informasi pada suatu titik di dalam blok dasar.
Setiap jenis tertentu dari data-aliran analisis telah mentransfer sendiri fungsi dan bergabung dengan operasi. Beberapa data-aliran masalah, analisis arus mundur. Ini mengikuti rencana yang sama, kecuali bahwa fungsi transfer diterapkan kepada negara keluar menghasilkan negara masuk, dan operasi bergabung bekerja pada masuknya negara penerus untuk menghasilkan negara keluar.
Titik masuk (aliran ke depan) memainkan peran penting: Karena tidak memiliki pendahulu, masuknya negara didefinisikan dengan baik pada awal analisis. Misalnya, himpunan variabel lokal dengan nilai-nilai diketahui kosong. Jika grafik aliran kontrol tidak mengandung siklus (tidak ada loop eksplisit atau implisit dalam prosedur) memecahkan persamaan secara langsung. Grafik aliran kontrol kemudian dapat topologi diurutkan, berjalan dalam urutan seperti ini, negara-negara entri dapat dihitung pada awal setiap blok, karena semua pendahulu dari blok yang telah diproses, sehingga mereka menyatakan keluar tersedia. Jika grafik aliran kontrol tidak mengandung siklus, sebuah algoritma yang lebih canggih diperlukan.[Sunting] Sebuah algoritma iteratif
Cara yang paling umum untuk memecahkan persamaan aliran data adalah dengan menggunakan algoritma iteratif. Ini dimulai dengan perkiraan negara di-blok masing-masing. Out-negara tersebut kemudian dihitung dengan menerapkan fungsi transfer pada di negara-negara. Dari ini, di-negara yang diperbarui dengan menerapkan operasi bergabung. Dua terakhir langkah ini diulang sampai kita mencapai fixpoint disebut: situasi di mana di negara-negara (dan keluar-negara bagian di konsekuensi) tidak berubah.
Sebuah algoritma dasar untuk memecahkan persamaan aliran data adalah round-robin algoritma iteratif:
untuk i ← 1 sampai N
menginisialisasi node i
sementara (set masih berubah)
untuk i ← 1 sampai N
recompute set pada node i
[Sunting] Konvergensi
Untuk digunakan, pendekatan iteratif harus benar-benar mencapai suatu fixpoint. Hal ini dapat dijamin oleh memaksakan kendala pada kombinasi dari domain nilai negara, fungsi transfer dan operasi join.
Nilai domain harus urutan parsial dengan ketinggian yang terbatas (yaitu, tidak ada rantai ascending terbatas x1 <x2 <...). Kombinasi dari fungsi transfer dan operasi harus bergabung monoton sehubungan dengan urutan parsial. Kemonotonan memastikan bahwa pada setiap iterasi nilai baik akan tetap sama atau akan tumbuh lebih besar, sementara tingginya terbatas memastikan bahwa hal itu tidak bisa tumbuh tanpa batas. Dengan demikian kita akhirnya akan mencapai situasi di mana T (x) = x untuk semua x, yang fixpoint tersebut.[Sunting] Pendekatan daftar pekerjaan
Sangat mudah untuk memperbaiki algoritma di atas dengan memperhatikan bahwa di negara-blok tidak akan berubah jika keluar-negara pendahulunya tidak berubah. Oleh karena itu, kami memperkenalkan sebuah daftar kerja: daftar blok yang masih harus diproses. Setiap kali keluar-negara perubahan blok, kita menambahkan penerus ke daftar kerja. Dalam setiap iterasi, blok dihapus dari daftar pekerjaan. Its keluar-negara dihitung. Jika out-negara berubah, penerus blok tersebut ditambahkan ke daftar kerja. Untuk efisiensi, blok tidak boleh dalam daftar bekerja lebih dari sekali.
Algoritma ini dimulai dengan menempatkan titik masuk dalam daftar pekerjaan. Ini berakhir ketika daftar pekerjaan kosong.[Sunting] Perintah penting
Efisiensi iteratif memecahkan persamaan aliran data dipengaruhi oleh urutan di mana node lokal dikunjungi. Selain itu, tergantung, apakah data-aliran persamaan yang digunakan untuk maju atau mundur aliran data analisis atas CFG tersebut. Intuitif, dalam masalah aliran ke depan, akan tercepat jika semua pendahulu dari blok telah diproses sebelum blok itu sendiri, sejak saat iterasi akan menggunakan informasi terbaru. Dengan tidak adanya loop adalah mungkin untuk memesan blok sedemikian rupa sehingga benar keluar-negara dihitung dengan memproses setiap blok hanya sekali.
Dalam berikut, pesanan beberapa iterasi untuk menyelesaikan persamaan aliran data yang dibahas (sebuah konsep yang berhubungan untuk memesan iterasi dari CFG adalah pohon traversal dari pohon).
Urutan acak - Ini pesanan iterasi tidak menyadari apakah data-aliran persamaan memecahkan masalah data aliran maju atau mundur. Oleh karena itu, kinerja yang relatif miskin dibandingkan dengan perintah iterasi khusus.
Postorder - Ini adalah perintah iterasi khas untuk mundur data masalah arus. Dalam iterasi postorder, node dikunjungi setelah semua node penggantinya telah dikunjungi. Biasanya, iterasi postorder diimplementasikan dengan strategi depth-first.
Sebaliknya postorder - Ini adalah perintah iterasi khas untuk meneruskan data-masalah arus. Dalam reverse-postorder iterasi, node dikunjungi sebelum semua node penggantinya telah dikunjungi, kecuali bila penggantinya adalah dicapai oleh ujung belakang. (Catatan bahwa ini tidak sama dengan preorder.)
[Sunting] Inisialisasi
Nilai awal di-negara adalah penting untuk mendapatkan hasil yang benar dan akurat. Jika hasilnya digunakan untuk optimasi compiler, mereka harus memberikan informasi yang konservatif, yaitu ketika menerapkan informasi, program tidak harus mengubah semantik. Iterasi dari algoritma fixpoint akan mengambil nilai-nilai dalam arah elemen maksimum. Menginisialisasi semua blok dengan elemen maksimum karena itu tidak berguna. Setidaknya satu blok dimulai di negara dengan nilai kurang maksimal. Rincian tergantung pada masalah data-aliran. Jika elemen minimal merupakan informasi benar-benar konservatif, hasilnya dapat digunakan dengan aman bahkan selama iterasi data aliran. Jika itu merupakan informasi yang paling akurat, fixpoint harus dicapai sebelum hasil dapat diterapkan.[Sunting] Contoh
Berikut ini adalah contoh dari sifat-sifat dari program komputer yang dapat dihitung dengan data-aliran analisis. Perhatikan bahwa sifat dihitung dengan analisis aliran data biasanya hanya perkiraan sifat nyata. Hal ini karena data-flow analisis beroperasi pada struktur sintaksis CFG tanpa simulasi aliran kontrol yang tepat dari program. Namun, untuk menjadi masih berguna dalam praktek, algoritma analisis data flow biasanya dirancang untuk menghitung masing-masing pendekatan bawah atas sifat program nyata.[Sunting] Analisis Teruskan
Analisis Definisi mencapai menghitung untuk setiap titik program set definisi yang berpotensi dapat mencapai titik ini program.
1: jika b == 4 maka2: a = 5;3: lain4: a = 3;5: endif6:7: jika <4 maka8: ...
Definisi mencapai variabel "a" pada baris 7 adalah himpunan tugas a = 5 pada baris 2 dan a = 3 pada baris 4.[Sunting] Analisis Mundur
Analisis variabel tinggal menghitung untuk setiap titik program variabel yang mungkin berpotensi dibaca kemudian sebelum update menulis berikutnya. Hasilnya adalah biasanya digunakan oleh eliminasi kode mati untuk menghapus pernyataan yang menetapkan ke suatu variabel yang nilainya tidak digunakan sesudahnya.
Di-negara blok adalah himpunan variabel yang tinggal di ujung blok. Its luar negara adalah serangkaian variabel yang ada tinggal pada awal itu. Di-negara adalah gabungan dari out-negara dari blok penerus. Fungsi transfer dari sebuah pernyataan diterapkan dengan membuat variabel yang ditulis mati, kemudian membuat variabel yang dibaca hidup.
/ / Keluar: {}b1: a = 3;
b = 5;
d = 4;
jika a> b maka
/ / Dalam: {a, b, d}
/ / Keluar: {a, b}b2: c = a + b;
d = 2;
/ / Dalam: {b, d}
/ / Keluar: {b, d}b3: endif
c = 4;
kembali b * d + c;
/ / Dalam: {}
Out-negara b3 hanya berisi b dan d, karena c telah ditulis. Di negara-b1 adalah gabungan dari out-negara bagian b2 dan b3. Definisi c dalam b2 dapat dihapus, karena c adalah tidak hidup segera setelah pernyataan itu.
Memecahkan persamaan aliran data dimulai dengan menginisialisasi semua di-negara-negara dan keluar ke set kosong. Daftar kerja diinisialisasi dengan memasukkan titik keluar (B3) dalam daftar pekerjaan (khas untuk mengalir ke belakang). Dihitung nya keluar-negara berbeda dari yang sebelumnya, sehingga pendahulunya b1 dan b2 dimasukkan dan proses berlanjut. Kemajuan tersebut diringkas dalam tabel di bawah ini.pengolahan di negara-negara lama keluar baru keluar-negara daftar pekerjaanb3 {} {} {b, d} (b1, b2)b1 {b, d} {} {} (b2)b2 {b, d} {} {a, b} (b1)b1 {a, b, d} {} {} ()
Catatan b1 yang masuk dalam daftar sebelum b2, b1 pengolahan yang memaksa dua kali (b1 adalah kembali dimasukkan sebagai pendahulu dari b2). Memasukkan b1 b2 sebelumnya akan membiarkan selesai sebelumnya.
Menginisialisasi dengan himpunan kosong adalah inisialisasi optimis: semua variabel dimulai sebagai mati. Perhatikan bahwa keluar-negara tidak dapat menyusut dari satu iterasi ke depan, meskipun keluar-negara dapat lebih kecil yang di-negara. Hal ini dapat dilihat dari fakta bahwa setelah iterasi pertama keluar-satunya negara dapat berubah dengan perubahan negara dalam-. Karena di negara dimulai sebagai himpunan kosong, hanya dapat tumbuh di iterasi lebih lanjut.[Sunting] Pendekatan-pendekatan lain
Pada tahun 2002, Markus Mohnen dijelaskan metode baru data-flow analisis yang tidak memerlukan konstruksi eksplisit dari sebuah grafik aliran data, [2], bukan mengandalkan pada interpretasi abstrak program dan menjaga working set counter program. Pada setiap cabang kondisional, baik target ditambahkan ke working set. Masing-masing jalan diikuti untuk sebagai petunjuk sebanyak mungkin (sampai akhir program atau sampai telah dilingkarkan dengan tidak ada perubahan), dan kemudian dihapus dari set dan program counter berikutnya diambil.[Sunting] Bit masalah vektor
Contoh di atas adalah masalah di mana nilai data-aliran set, misalnya set definisi mencapai (Menggunakan sedikit untuk posisi definisi dalam program), atau set variabel hidup. Set ini dapat direpresentasikan secara efisien sebagai vektor bit, di mana setiap bit mewakili keanggotaan set satu elemen tertentu. Menggunakan representasi ini, fungsi bergabung dan transfer dapat diimplementasikan sebagai operasi bitwise logis. Operasi bergabung biasanya serikat buruh atau persimpangan, dilaksanakan oleh bitwise logis atau dan logis dan. Fungsi transfer untuk setiap blok dapat diuraikan dalam apa yang disebut gen dan membunuh set.
Sebagai contoh, dalam hidup-variabel analisis, operasi bergabung adalah serikat. Set membunuh adalah himpunan variabel yang ditulis dalam blok, sedangkan set gen adalah himpunan variabel yang dibaca tanpa tertulis pertama. Data-aliran persamaan menjadi
out_b = \ bigcup_ {s \ di succ_b} in_s
in_b = (out_b - kill_b) \ cangkir gen_b
Dalam operasi logis, ini berbunyi sebagai
keluar (b) = 0
untuk s di succ (b)
keluar (b) = keluar (b) atau (s)
dalam (b) = (keluar (b) dan tidak membunuh (b)) atau gen (b)
[Sunting] Sensitivitas
Analisis aliran data secara inheren aliran-sensitif. Analisis aliran data biasanya jalan-insensitive, meskipun mungkin untuk mendefinisikan data flow persamaan yang menghasilkan jalur-sensitif analisis.
Aliran-sensitif analisis memperhitungkan urutan pernyataan dalam program. Sebagai contoh, aliran-insensitive analisis alias pointer dapat menentukan "variabel x dan y dapat merujuk ke lokasi yang sama", sementara analisis aliran-sensitif dapat menentukan "setelah pernyataan 20, variabel x dan y dapat merujuk ke lokasi yang sama".
Sebuah jalur-sensitif analisis menghitung potongan informasi yang berbeda tergantung pada analisis predikat di instruksi cabang bersyarat. Sebagai contoh, jika cabang berisi kondisi x> 0, maka pada musim gugur-melalui jalan setapak, analisis akan berasumsi bahwa x <= 0 dan pada target cabang itu akan berasumsi bahwa memang x> 0 berlaku.
Sebuah konteks-sensitif analisis adalah analisis interprosedural yang mempertimbangkan konteks menelepon ketika menganalisis target dari pemanggilan fungsi. Secara khusus, menggunakan informasi konteks yang dapat melompat kembali ke situs panggilan asli, sedangkan tanpa informasi itu, analisis informasi harus disebarkan kembali ke semua situs panggilan mungkin, berpotensi kehilangan presisi.
Sumber : Wikipedia
Branch Prediction
Peregangan IBM, dirancang pada 1950-an, pra-dieksekusi semua cabang bersyarat dan setiap cabang kondisional yang tergantung pada register indeks. Untuk cabang kondisional lainnya, model produksi pertama dua diimplementasikan memprediksi untaken; model selanjutnya diubah untuk menerapkan prediksi yang didasarkan pada nilai-nilai saat ini dari bit indikator (sesuai dengan kode kondisi saat ini) Para desainer Peregangan telah dianggap bit sedikit statis dalam. instruksi cabang pada awal proyek tetapi memutuskan melawan mereka. Pemulihan Misprediction disediakan oleh unit lookahead pada Stretch, dan bagian dari reputasi Peregangan untuk yang kurang-bintang kinerja disalahkan pada waktu yang dibutuhkan untuk pemulihan misprediction. Selanjutnya IBM desain komputer yang besar tidak menggunakan prediksi cabang dengan eksekusi spekulatif sampai IBM 3090 pada tahun 1985.
Prediktor Dua-bit diperkenalkan oleh Tom McWilliams dan Curt Widdoes pada tahun 1977 untuk Lawrence Livermore National Lab S-1 superkomputer dan mandiri oleh Jim Smith pada tahun 1979 di CDC .
Prosesor Microprogrammed, populer dari tahun 1960 ke tahun 1980-an dan seterusnya, mengambil beberapa siklus per instruksi, dan umumnya tidak memerlukan prediksi cabang. Namun, bersama dengan IBM 3090, ada beberapa contoh desain microprogrammed prediksi cabang yang dimasukkan.
Burroughs B4900, mesin COBOL microprogrammed dirilis pada ~ 1982 adalah pipelined dan digunakan prediksi cabang. Para B4900 cabang prediksi sejarah negara disimpan kembali ke dalam memori instruksi selama pelaksanaan program. Para B4900 dilaksanakan 4-negara cabang prediksi dengan menggunakan 4 opkode cabang semantik setara untuk mewakili setiap jenis operator yang cabang. Opcode digunakan menunjukkan sejarah yang instruksi cabang tertentu. Jika perangkat keras ditentukan bahwa keadaan prediksi cabang cabang tertentu harus diperbarui, itu akan menulis ulang opcode dengan opcode semantik setara yang mengisyaratkan sejarah yang tepat. Skema ini memperoleh hit rate 93%. US patent 4.435.756 dan yang lainnya diberikan pada skema ini.
VAX 9000, diumumkan pada tahun 1989, adalah baik microprogrammed dan pipelined, dan melakukan prediksi cabang. [14]
Komersial pertama prosesor RISC, MIPS R2000 dan R3000 dan prosesor SPARC sebelumnya, tidak hanya sepele "tidak-diambil" prediksi cabang. Karena mereka menggunakan slot cabang keterlambatan, mengambil hanya satu instruksi per siklus, dan dieksekusi di-order, tidak ada kerugian kinerja. Kemudian, R4000 menggunakan sepele yang sama "tidak-diambil" prediksi cabang, dan kehilangan dua siklus untuk setiap cabang diambil karena kekambuhan resolusi cabang empat siklus panjang.
Prediksi cabang menjadi lebih penting dengan pengenalan prosesor superscalar pipelined seperti Intel Pentium, DEC Alpha 21064, MIPS R8000, dan seri IBM POWER. Prosesor ini semua bergantung pada satu bit atau prediktor bimodal sederhana.
Alpha DEC 21264 (EV6) menggunakan prediktor berikutnya garis diganti oleh prediktor lokal gabungan dan prediktor global, di mana pilihan menggabungkan dibuat oleh prediksi bimodal.
Para K8 AMD memiliki prediktor bimodal dan global gabungan, di mana pilihan menggabungkan lain prediktor bimodal. Cache prosesor ini dasar dan counter bimodal pilihan prediktor dalam bit dari L2 cache ECC lain digunakan untuk. Akibatnya, ia memiliki basis yang sangat luas efektif dan tabel pilihan prediktor, dan paritas daripada ECC pada instruksi dalam cache L2. Paritas baik-baik saja, karena setiap instruksi menderita kesalahan paritas dapat diremehkan dan refetched dari memori.
Alpha 21464 [15] (EV8, dibatalkan akhir dalam desain) memiliki cabang misprediction hukuman minimal 14 siklus. Ini adalah untuk menggunakan prediktor garis kompleks tapi cepat selanjutnya diganti oleh bimodal gabungan dan suara mayoritas-prediktor. Suara mayoritas adalah antara bimodal dan dua prediktor gskew.
Prediktor Dua-bit diperkenalkan oleh Tom McWilliams dan Curt Widdoes pada tahun 1977 untuk Lawrence Livermore National Lab S-1 superkomputer dan mandiri oleh Jim Smith pada tahun 1979 di CDC .
Prosesor Microprogrammed, populer dari tahun 1960 ke tahun 1980-an dan seterusnya, mengambil beberapa siklus per instruksi, dan umumnya tidak memerlukan prediksi cabang. Namun, bersama dengan IBM 3090, ada beberapa contoh desain microprogrammed prediksi cabang yang dimasukkan.
Burroughs B4900, mesin COBOL microprogrammed dirilis pada ~ 1982 adalah pipelined dan digunakan prediksi cabang. Para B4900 cabang prediksi sejarah negara disimpan kembali ke dalam memori instruksi selama pelaksanaan program. Para B4900 dilaksanakan 4-negara cabang prediksi dengan menggunakan 4 opkode cabang semantik setara untuk mewakili setiap jenis operator yang cabang. Opcode digunakan menunjukkan sejarah yang instruksi cabang tertentu. Jika perangkat keras ditentukan bahwa keadaan prediksi cabang cabang tertentu harus diperbarui, itu akan menulis ulang opcode dengan opcode semantik setara yang mengisyaratkan sejarah yang tepat. Skema ini memperoleh hit rate 93%. US patent 4.435.756 dan yang lainnya diberikan pada skema ini.
VAX 9000, diumumkan pada tahun 1989, adalah baik microprogrammed dan pipelined, dan melakukan prediksi cabang. [14]
Komersial pertama prosesor RISC, MIPS R2000 dan R3000 dan prosesor SPARC sebelumnya, tidak hanya sepele "tidak-diambil" prediksi cabang. Karena mereka menggunakan slot cabang keterlambatan, mengambil hanya satu instruksi per siklus, dan dieksekusi di-order, tidak ada kerugian kinerja. Kemudian, R4000 menggunakan sepele yang sama "tidak-diambil" prediksi cabang, dan kehilangan dua siklus untuk setiap cabang diambil karena kekambuhan resolusi cabang empat siklus panjang.
Prediksi cabang menjadi lebih penting dengan pengenalan prosesor superscalar pipelined seperti Intel Pentium, DEC Alpha 21064, MIPS R8000, dan seri IBM POWER. Prosesor ini semua bergantung pada satu bit atau prediktor bimodal sederhana.
Alpha DEC 21264 (EV6) menggunakan prediktor berikutnya garis diganti oleh prediktor lokal gabungan dan prediktor global, di mana pilihan menggabungkan dibuat oleh prediksi bimodal.
Para K8 AMD memiliki prediktor bimodal dan global gabungan, di mana pilihan menggabungkan lain prediktor bimodal. Cache prosesor ini dasar dan counter bimodal pilihan prediktor dalam bit dari L2 cache ECC lain digunakan untuk. Akibatnya, ia memiliki basis yang sangat luas efektif dan tabel pilihan prediktor, dan paritas daripada ECC pada instruksi dalam cache L2. Paritas baik-baik saja, karena setiap instruksi menderita kesalahan paritas dapat diremehkan dan refetched dari memori.
Alpha 21464 [15] (EV8, dibatalkan akhir dalam desain) memiliki cabang misprediction hukuman minimal 14 siklus. Ini adalah untuk menggunakan prediktor garis kompleks tapi cepat selanjutnya diganti oleh bimodal gabungan dan suara mayoritas-prediktor. Suara mayoritas adalah antara bimodal dan dua prediktor gskew.
Perbedaan Organisasi Komputer & Arsitektur Komputer
Organisasi Komputer :
- Bagian yang terkait erat dengan unit–unit operasional
- Contoh: teknologi hardware, perangkat antarmuka, teknologi memori, sistem memori, dan sinyal–sinyal kontrol
- atribut–atribut sistem komputer yang terkait dengan seorang programmer
- Contoh: set instruksi, aritmetika yang digunakan, teknik pengalamatan, mekanisme I/O
Rabu, 06 April 2011
Ponsel Pertama Di Dunia,Wow!
Inilah ponsel yg ukurannya sebesar tutup tempat sampah tetapi ponsel ini cuma memiliki jangkauan setengah mil.
Dilihat dari segi design dan ukuran, ponsel pertama di dunia ini amad jauuuuhhhh berbeda sama ponsel masa kini, yg cukup kecil untuk menyelinap di saku dan dapat menghubungi hampir kemana saja di dunia ini. Tapi dari sini lah telepon nirkabel bermula.
Dilihat dari segi design dan ukuran, ponsel pertama di dunia ini amad jauuuuhhhh berbeda sama ponsel masa kini, yg cukup kecil untuk menyelinap di saku dan dapat menghubungi hampir kemana saja di dunia ini. Tapi dari sini lah telepon nirkabel bermula.
Sang pencipta sendiri, Nathan Stubblefield akhirnya diakui sebagai bapak teknologi telepon seluler tepat 100 tahun setelah ia mempatenkan desain tersebut untuk sebuah "telepon nirkabel"
Nathan Stubbefield sebenarnya hanyalah petani melon biasa yg sangat menyukai IPTEK bahkan dia telah menemukan radio sebelum Nikola Tesla atau Guglielmo Marcon tetapi radio yg dia temukan menggunakan frekuensi audio induksi, dikarenakan radio induksi menyebabkan gangguan pada wilayah sekitarnya sehingga kalah populer dengan radio transmisi yg di temukan oleh Nikola Tesla atau Guglielmo Marcon.
Pada tahun 1902 petani melon ini datang dengan penemuannya, setelah mengorbankan setiam jam menit dan detik demi untuk membuat jaringan telekomunikasi di kampung halamannya Murray, Kentucky.
Note: Nathan Stubbefield menunjukan penemuannya (dapat dilihat tiang di tengah gambar)
Dia membangung 120 kaki tiang di kebun, yg dapat mentransfer percakapan dari satu telepon ke telepon yg lain dengan menggunakan medan magnet.
Dia mendemonstrasikan temuannya di alun-alun kota pada hari Tahun Baru 1902.
Pada tahun 1908 dia mematenkan telepon nirkabel versi baru untuk berkomunikasi dengan kendaraan bergerak.
Sayangnya telepon nirkabel tidak sukses dalam masa hidupnya,dia meninggal dengan keadaan miskin pada tahun 1928.
Tapi sekarang dia telah diakui sebagai "Father of The Modern Mobile Phone" ,bahkan Virgin Mobile membuat page khusus untuk menandai ulang tahun temuan Nathan Stubbefield di website resmi nya.
sumber :kaskus.us
Alasan Adanya saku Kecil Pada Celana Jeans
Pernah tidak terlintas kenapa celana jeans selalu ada saku kecil di bagian sebelah kanannya? Selintas saku kecil ini tak ada fungsinya selain hanya tempelan untuk menambah aksentuasi gaya pemakainya, atau mungkin ciri khas celana jeans. Namun, dari saku imut-imut inilah sebenarnya bisa dibaca sejarah celana yang dipopulerkan oleh Levi Strauss tahun 1880 ini, delapan tahun setelah jeans masuk ke Amerika Serikat (AS) tahun 1872.
Sebagai jenis tekstil, jeans pertama kali dibuat di Genoa, Italia tahun 1560-an. Kain celana ini biasa dipakai oleh angkatan laut. Orang Prancis menyebut celana ini dengan sebutan "bleu de Génes", yang berarti biru Genoa. Meski tekstil ini pertama kali diproduksi dan dipakai di Eropa, tetapi sebagai fashion, jeans dipopulerkan di AS oleh Levi Strauss, seorang pemuda berusia dua puluh tahunan yang mengadu peruntungannya ke San Francisco sebagai pedagang pakaian. Ketika itu, AS sedang dilanda demam emas.
Akan tetapi, sampai di California semua barangnya habis terjual, kecuali sebuah tenda yang terbuat dari kain kanvas. Kain kanvas ini dipotongnya dan dibuatnya menjadi beberapa celana yang dijual pada para pekerja tambang emas. Dan ternyata para pekerja menyukainya karena celana buatan Strauss tahan lama dan tak mudah koyak. Merasa mendapat peluang, Strauss menyempurnakan "temuannya" dengan memesan bahan dari Genoa yang disebut "Genes", yang oleh Strauss diubah menjadi "Blue Jeans".
Di sinilah para penambang tambah menyukai celana buatan Strauss dan "menobatkan" celana itu sebagai celana resmi para penambang. Para penambang emas itu menyebut celana Strauss dengan "those pants of Levi`s" atau "Celana Si Levi". Sebutan inilah yang mengawali merek dagang pertama celana jeans pertama di dunia.
Naluri bisnis Strauss yang tajam membuatnya mengajak pengusaha sukses Jakob Davis untuk bekerja sama, dan pada tahun 1880 kerja sama itu melahirkan pabrik celana jeans pertama. Dan produk desain mereka yang pertama adalah "Levi`s 501".
Produk desain pertama memang dikhususkan bagi para penambang emas. Celana ini memiliki 5 saku, 2 di belakang dan 2 di depan, dan 1 saku kecil dalam saku depan sebelah kanan. Karena diperuntukkan bagi para penambang, saku ini tentu bukan untuk bergaya-ria. Tetapi saku imut-imut ini dirancang untuk menyimpan butiran-butiran emas yang berukuran kecil. Meski kini jeans diproduksi dalam berbagai merek dan bukan hanya untuk para penambang, tetapi saku imut-imut itu tetap ada. Tentu saja fungsinya bukan sebagai tempat menyimpan butiran emas.
sumber :http://www.strov.co.cc/2010/02/alasan-adanya-saku-kecil-pada-celana.html