Jumat, 05 Agustus 2011

Teknik optimasi dan Tabel Informasi


TEKNIK OPTIMASI

Dependensi optimasi. Tahapan optimasi kode bertujuan untuk menghasilkan kode program yang berukuran lebih kecil dan lebih cepat eksekusinya. Berdasarkan ketergantungannya pada mesin, optimasi dibagi menjadi :
  1. Machine Dependent Optimizer. Kode dioptimasi sehingga lebih efisien pad mesin tertentu. Optimasi ini memerlukan informasi mengenai feature yang ada pada mesin tujuan dan mengambil keuntungan darinya untuk menghasilkan kode yang lebih pendek atau dieksekusi lebih cepat.
  2. Machine Independent Optimizer. Strategi optimasi yang bisa diaplikasikan tanpa tergantung pada mesin tujuan tempat kode yang dihasilkan akan dieksekusi nantinya. Mesin ini meliputi optimasi lokal dan optimasi global.

Optimasi Lokal adalah optimasi yang dilakukan hanya pada suatu blok dari source code, cara-caranya sebagai berikut:
  1. Folding. Mengganti konstansta atau ekspresi yang bisa dievaluasi pada saat compile time dengan nilai komputasinya. Misalkan Instruksi ;
A:=2+3+B
bisa diganti menjadi
A:=5+B
  1. Redundant-Subexpression Elimination. Sebuah ekspresi yang sudah pernah dikomputasi, digunakan lagi hasilnya, ketimbang melakukan komputasi ulang. Misalkan terdapat urutan instruksi :
A:=B+C
X:=Y+B+C
kemunculan kedua dari B+C yang redundan bisa diatasi dengan memanfaatkan hasil komputasinya yang sudah ada pada instruksi sebelumnya. Perhatikan, hal ini bisa dilakukan dengan catatan belum ada perubahan pada variabel yang berkaitan.
  1. Optimisasi dalam sebuah iterasi.
  Loop Unrolling: Menggantikan suatu loop dengan menulis statement dalam loop beberapa kali. Hal ini didasari pemikiran, sebuah iterasi pada implementasi level rendah akan memerlukan operasi sebagai berikut.
      Inisialisasi/pemberian nilai awal pada variabel loop. Dilakukan sekali pada saat permulaan eksekusi loop.
      Pengujian, apakah variabel loop telah mencapai kondisi terminasi.
      Adjustment yaitu penambahan atau pengurangan nilai pada variabel loop dengan jumlah tertentu.
      Operasi yang terjadi pada tubuh perulangan (loop body).
Dalam setiap perulangan akan terjadi pengujian dan adjusment yang menambah waktu eksekusi. Contoh pada instruksi :
FOR I:=1 to 2 DO
A[I]:=0;
terdapat instruksi untuk inisialisasi I menjadi 1. serta operasi penambahan nilai/increment 1 dan pengecekan variabel I pada setiap perulangan. Sehingga untuk perulangan saja memerlukan lima instruksi, ditambah dengan instruksi assignment pada tubuh perulangan menjadi tujuh instruksi. Dapat dioptimasikan menjadi :
A[1]:=0;
A[2]:=0;
yang hanya memerlukan dua instruksi assignment saja. Untuk menentukan optimasi ini perlu dilihat perbandingan kasusnya dengan tanpa melakukan optimasi.
  Frequency Reduction: Pemindahan statement ke tempat yang lebih jarang dieksekusi. Contoh:
FOR I:=1 TO 10 DO
BEGIN
X:=5;
A:=A+I;
END;
kita ,melihat bawa tidak terjadi perubahan /manipulasi pada variabel X didalam iterasi, karena itu kita bisa mengeluarkan instruksi tersebut keluar iterasi, menjadi:
X:=5;
FOR I:=1 TO 10 DO
BEGIN
A:=A+I
END;
  1. Strength Reduction. Penggantian suatu operasi dengan jenis operasi lain yang lebih cepat dieksekusi. Misalkan pada beberapa komputer operasi perkalian memerlukan waktu lebih banyak untuk dieksekusi dari pada operasi penjumlahan, maka penghematan waktu bisa dilakukan dengan mengganti operasi perkalian tertentu dengan penjumlahan. Contoh lain, instruksi :
A:=A+1;
dapat digantikan dengan: INC(A);

OPTIMISASI GLOBAL

Optimisasi global biasanya dilakukan dengan analisis flow, yaitu suatu graf berarah yang menunjukkan jalur yang mungkin selama dieksekusi program. Kegunaannya adalah sebagai berikut:
a)      Bagi pemrogram menginformasikan :
  Unreachable/dead code: kode yang tidak akan pernah dieksekusi. Misalnya terdapat urutan instruksi:
X:=5;
IF X:=0 THEN
A:=A+1
Instruksi A:=A+1 tidak akan pernah dieksekusi
  Unused parameter pada prosedur: parameter yang tidak akan pernah digunakan didalam prosedur. Contohnya :
Procedure Jumlah (a,b,c:integer);
var x: integer
begin
x:=a+b
end;
kita lihat parameter c tidak pernah digunakan didalam prosedur, sehingga seharusnya tidak perlu diikutrestakan.
  Unused Variable: Variabel yang tidak pernah dipakai dalam program. Contohnya :
Program Pendek;
var a,b:integer;
begin
a:=5;
end;
variabel b tidak pernah digunakan dalam program sehingga bisa dihilangkan.
  Variabel yang dipakai tanpa nilai awal. Contohnya:
Program awal;
var a,b: integer;
begin
a:=5;
a:=a+b;
end;
kita lihat variabel b digunakan tanpa memiliki nilai awal/belum di-assign.
b)      Bagi kompilator:
  Meningkatkan efisiensi eksekusi program.
  Menghilangkan useless code/kode yang tidak terpakai.

TABEL INFORMASI

Tabel Informasi atau tabel simbol dibuat guna mempermudah pembuatan dan implementasi dari semantic analyzer. Tabel simbol ini mempunyai dua fungsi penting dalam proses translasi, yaitu:
Dua fungsi penting :
1.      Untuk membantu pemeriksaan kebenaran dari program sumber
2.      Untuk membantu dan mempermudah intermediate code dan proses pembangkitan kode
Beberapa jenis tabel informasi :
1.      Tabel Identifier , berfungsi menampung semua identifier yang terdapat dalam prgram
TabId:Array [0..tabmax] of record
2.      Tabel Array, berfungsi menampung informasi tambahan untuk sebuah array
TabArray: array [1..tabmax] of record
3.      Tabel Blok , mencatat variable-variable yang ada pada blok yang sama
Tabblok:array [1..tabmax] of record
4.      Tabel Real , menyimpan elemen tabel bernilai real
TabReal: array [1..tabmax] of record
5.      Tabel string, menyimpan informasi string
TabString: array [1..tabmax] of string
6.      Tabel display , mencatat blok yang aktif
TabDisplay: array [1..tabmax] of integer

Pengaturan runtime environment


PENGATURAN RUNTIME ENVIRONMENT
6.1  Penetapan runtime storage adalah tempat untuk menyimpan data dari sumber ketika eksekusi program.Ada dua macam penetapan runtime storage yaitu penetapan statis dan penetapan dinamis.
·         Alokasi Full –Statis
contoh: Fortran
ü  semua dialokasikan olehkompiler padawaktu kompilasi
ü  Tidak mendukung pointer
ü  Tidak membutuhkan stack
ü  tidak ada rekursi dan alokasi memori secara dinamis
ü  digunakan untuk: variable global, konstanta
ü  Berarti pada suatu saat hanya boleh ada satu record aktivasi yang aktif
·         Alokasi dinamis :
Ada dua macam penetapan dinamis :
o   Penetapan dinamis untuk stack
contoh: high level language= C, C++, Pascal
ü  tempat penyimpanan diatur sebagai suatu stack
ü  biasa digunakan untuk prosedur rekursif dan pointer (alokasi dinamis)
ü  Pada suatu saat boleh banyak record aktivasi aktif
o   Penetapan dinamis untuk heap :
contoh: Lisp, Java danScheme
ü  mengalokasikan dan mendealokasikan tempat penyimpanan seperlunya.
ü  Biasanya menggunakan heap (karenadinamis)
ü  Dibutuhkan garbage collection dan compaction untuk memperoleh kembali space yang dibutuhkan.
ü  Beberapa kemungkinan dealokasi(tidak ada dealokasi,explixit dealocation dan implicit dealocation).
6.2  Karena hal ini berhubungan dengan pemanggilan prosedur.Setiap saat prosedur dipanggil dan      akan mengacu pada data statis yang sama.

6.3  Activation record adalah ruang penyimpanan yang digunakan untuk variabel-   variabel.Komponen- komponen yang ada dalam activation record adalah :
·       Parameter yang sesuai dengan prosedur
·         Penyimpanan informasi (bookkeeping information), termasuk return address.
·         Ruang untuk variabel lokal
·         Ruang untuk lokal temporaries tersusun atas compiler untuk menyimpan nilai-nilai subexpression.

Record aktivasi(activation record) berisi informasi yang dibutuhkan untuk mengatur aktivasi sebuah prosedur yang terdiri dari beberapa field:
·         Return value (nilai kembalian), dari prosedur yang dipanggil keprosedur pemanggilnya.
·         Parameter aktual, yang dipakai oleh prosedur pemanggil untuk memberikan parameter kepada prosedur yang dipanggil.
·         Link kendali aktivasi,yang menunjuk pada record aktivasi pemanggil
·         Link akses pemanggil, yang berguna sebagai tempat untuk menyimpan data non local milik record aktivasi lain.
·         Address
·         Current adress
·         Return address
·         Start address, danlain-lain
6.4   Pembuatan array nantinya akan berhubungan dengan besarnya alokasi penyimpanan Ukuran penyimpanan ini desesuaikan dengan tipe datanya. Misal tipe data byte : 1 byte.Susunan penyimpanan sangat tergantung dari mesin target.hal tersebut berhubungan dengan procedur dalam aktvation record.Dimana activation record berisi field-field.besarnya field-field ini ditentukan pada saat prosedur dipanggil pada saat kompilasi.

6.5  Pengiriman by value adalah pengiriman searah, dari program pemanggil fungsi ke fungsi yang dipanggilnya.Pengiriman by value dapat dilakukan untuk suatu statement, tidak hanya untuk suatu variabel, value, array atau konstanta saja.Saya tidak merekomendasikan bahasa C untuk menggunakan tipe passing call by value.karen call by value biasanya digunakan untuk variable non local dan parameter.
X
x,y,z
P
Q
R
6.6  Snapshot program :







6.7       Tampilan program dalam soal 6.6
X
x,y,z
P
Q
R
X
x,y,z

           




Bagaimana hal tersebut dapat membantu mempercepat pengeksekusian program?
Hal tersebut dapat membantu mempercepat pengeksekusian program Karena display adalah sebuah array  . Jumlah elemen pada display dihitung saat compile dengan memperkirakan kedalaman maksimum lexical nesting.

contoh soal 1


1. Yang termasuk jenis translator adalah
A. Compiler C.Kompilasi
B. Teknik D. Sintesa
Jawaban : A

2. + , - , x, a, b, dan ( , ) merupakan bagian dari symbol
a. Symbol operator c. Symbol tanda baca
b. Symbol terminal d. Huruf awal alphabet kecil
Jawaban : B

3. Yang tidak termasuk dari symbol non terminal adalah
a. +, - c. ( , )
b. Huruf besar awal alphabet A, B, C d. If, then, else
Jawaban : B

4. Derivasi akhir jika sentesial yang dihasilkan adalah sebuah kalimat. Pengertian tesebut adalah pengertian dari
a. Terminal c. Non terminal
b. Compile d. Kompilasi
Jawaban : A

5. Derivasi belum / tidak berakhir jika sentesial yang dihasilkan mengandung symbol
a. Terminal c. Compiler
b. Non terminal d. Kompilasi
Jawaban : B

6. Program yang membaca suatu bahasa pemograman dan menterjemahnya kedalam bahasa sasaran adalah fungsi dari
a. Compiler c. a dan b
b. Semantic d. a dan b salah
Jawaban : A

7. Proses kompilasi dikelompokan menjadi dua, yaitu
a. Analisa c. a dan b benar
b. Sintesa d. a dan b salah
Jawaban : C

8. Penganalisaan leksikal, penganalisa sintaks, penganalisa semantic termasuk dalam kelompok proses kompilasi
a. Sintesa c. hipotesis
b. Analisa d. automata
Jawaban : A

9. Membangun program sasaran yang diinginkan dari bentuk antara, berikut adalah pengertian dari
a. Kode c. analisa
b. Kompilator d. sintesa
Jawaban : D

10. Panjang maksimum ekspresi tunggal pada penganalisa semantic
a. 8 karakter c. 80 karakter
b. 24 karakter d. 64 karakter
Jawaban : C

11. Kelompok karakter yang membentuk sebuah token dinamakan
a. Lexeme c. ekspresi
b. Table d. identifier
Jawaban : A

12. Sederetan token yang tidak mengikuti aturan sintaks akan dilaporkan sebagai
a. Parse tree c. sintax directed
b. sintax eror d. komputasi
jawaban : B

13. membangkitkan kode pada bahasa target tertentu, berikut pengertian dari
a.pembangkit kode antara c. pengoptimal kode
b. pembangkit kode d. penganalisa semantic
jawaban : B