5/12/2014
Simulasi Simulasi: proses merancang model matematis atau logik dari
Pemodelan Sistem dan Simulasi AL-ASWIR
sistem selanjutnya melakukan eksperimen dengan model tsb untuk menggambarkan, menjelaskan dan memprediksi kelakukan dari sistem Kelebihan
Memungkinkan detail bisa dicakup Dapat membandingkan rancangan sistem yang lain Dapat mengontrol skala waktu Sistem eksisting tidak diperlukan
Kelemahan
Sulit untuk menggeneralisir hasil Sulit untuk mempertimbangkan semua nilai kasus/parameter Sulit untuk menentukan sensitivitas Waktu untuk mengembangkan dan mengeksekusi simulasi Upaya untuk memvalidasi model dan menganalisa data output
Definisi-Definisi Sistem
Definisi-Definisi Sistem
Definisi-Definisi Sistem Parameter – kuantitas yang tetap (fixed) atau dp dikontrol Variable – kuantitas yg ditentukan dari relasi-relasi fungsional
Computer system dan communication networks adalah dynamic
State Variables – set minimum dari variabel-variabel utk menggambarkan secara
lengkap suatu sistem pd suatu titik dlm waktu
Systems properties Static – state variables independen terhadap waktu Dynamic - state variables merupakan fungsi waktu Continuous time – states merupakan fungsi kontinyu dari waktu Discrete time -states hanya didefinisikan pd titik-titik waktu tertentu Combined – sistem mengandung baik variabel-variabel kontinyu dan diskrit
continuous time, discrete state, stochastic systems
Cat: states hanya dp memp. harga dari suatu range diskrit dan
konstan diantara perubahan
Titik waktu dimana state berubah suatu “event time’’ Apa yg menyebabkan state berubah disebut suatu ``event’’ Misalnya – kedatangan suatu packet ke suatu antrian router Sistem spt ini disebut Discrete Event Systems
Continuous State – state variables dp mempunyai harga dari suatu range kontinyu Discrete state – state variables hanya mempunyai harga dari range diskrit Deterministic - state variable dp diprediksi dg pasti Stochastic – state variables mengandung sumber randomness
Bagaimana Simulasi Berjalan (Programming Simulation)
Time-Based Simulation
Bagaimana simulasi berjalan … Time-driven: simulasi berjalan pd interval waktu tertentu/fixed
(mis. state ditentukan pada saat t, t + t, t + 2 t, …) Time-based simulation Event-driven: simulasi berjalan dari event-ke-event (mis. state
ditentukan pd titik waktu dari event berikutnya) Event-based simulation
1
5/12/2014
Mensimulasikan Discrete Event System
Event-Based Simulation
States
Kumpulan variabel-variabel yg diperlukan utk karakterisasi sistem pada sembarang titik waktu Entities
Objek-objek yg diproses dalam simulasi – mis. packet atau panggilan telepon Attributes
Karakteristik dari entities (mis., panjang paket, tipe dan tujuan) Resources
Substansi/items dimana entities menduduki atau menggunakan (mis., buffer space pd router, tokens pd FDDI network, bandwidth pd suatu link) Activities
Durasi waktu dimana panjangnya diketahui saat dimulai. Misalnya, waktu transmisi dari suatu paket pd suatu link Delay
Durasi waktu dg panjang yg tdk terspesifikasi yg tdk diketahui sebelum selesai. misalnya – waktu perjalanan suatu paket dari node A ke node B dlm suatu jaringan
Mensimulasikan Kelakuan Sistem Transient / Steady State Transient behavior : Suatu tipikal kelakuan sistem yg tergantung pd kondisi inisial (mis. booting up atau recovering dari suatu kegagalan komponen) Steady state behavior : kelakuan operasi normal dari sistem independent terhadap kondisi inisial
(Event
Pd event scheduled simulation – membangun model terdiri dari
identifikasi
(Event
Utk discrete event systems, state dari sistem hanya berubah pd saat
waktu event yg diskrit dlm titik waktu
Cat: state sistem akan tetap tdk berubah diantara waktu event Sistem dp disimulaikan dg mulai dari tiap event dlm waktu ke
event berikutnya dan menentukan efek apa dari event thd state sistem saat terjadi Utk mengimplementasikan suatu event scheduling simulasi memerlukan Simulation Clock Variabel memberikan nilai saat ini dari waktu yg disimulasikan Event List List dari waktu dan tipe dari tiap event masa depan/future event (diurut secara kronologis)
Simulasi packet loss pd suatu antrian router
Event-Based Simulation Scheduling Simulation)
Event-Based Simulation Scheduling Simulation)
Entities: Resources: States Events – dan efeknya pada state sistem
Simulasi mencakup pergi dari event time ke event time dan
menentukan efek pada state sistem – menghasilkan deretan snapshots dari kelakuan sistem Utk mengimplementasikan suatu event scheduling simulasi perlu membangun suatu event list, secara tdk langsung perlu membangun suatu deretan events Perhatikan contoh antrian single server – misalnya pada printer jaringan
Simulasi dg Tangan (Contoh) Perhatikan suatu sistem single server queueing Entities : print jobs (customers) Resources : printer (server of queue) State sistem: Jumlah dalam sistem ( antrian + sedang diservice )
n(t)
n(t) = {0, 1, 2, …} Status printer sp(t) busy : sp = 1
idle : sp = 0
Events ei : Job arrival ei = 1 Job departure ei = 2
2
5/12/2014
Efek Event pada State Sistem
Simulasi dg Tangan (Contoh) Menentukan input sistem – kita asumsikan waktu antar kedatangan
dan waktu service adalah random dengan fungsi densitas di bawah Job interarrival time
{ 1, 2, 2.5, 4, 4.5, 5.5 } dg equal prob sebesar 1/6 Job service time (printing time)
{ 1, 2, 3, 4 } dg prob 1/4 Mendefinisikan variabel ti = time of arrival IAi = interarrival time antara job ke (i-1) dan i Si = service time dari job ke i Dg membangkitkan deretan interarrival dan service times dari
fungsi densitas di atas kita dp
Simulasi dg Tangan (Contoh)
Simulasi dg Tangan (Contoh) Bangun event list dg mencari arrival times dan departure
times utk tiap-tiap job Dapatkan Waktu kedatangan (time of arrival)
ti = ti-1 + IAi waktu job i meninggalkan sistem (selesai printing)
jdi = bpi + Si waktu job i mulai dp service (start printing)
bpi = max{ ti , jdi-1}
Membangun Event List
Event List Penyusunan kronologis dari
event kedatangan dan kepergian bersamaan dg waktu/saat event – menghasilkan event list Simulasi berlangsung dg memproses event dari event list – menentukan efeknya pd state – kemudian bergerak ke waktu event berikutnya
3
5/12/2014
States Dari event list dp diplot state variabel vs waktu
Pengukuran Performansi Basis observasi Delay dlm sistem Response time Delay dlm queue Waiting time dll,, Statistik dicari dg standar sample mean, variance, dll…. Basis waktu Jumlah pelanggan dlm sistem Utilisasi server, dll. Statistik dicari dg rata-rata waktu integrasi
Pengukuran Performansi
Pengukuran Performansi
Contoh metrik performansi berbasis observasi
Contoh perata-rataan dlm waktu dari metrik performansi
Nilai rata-rata dari k pelanggan adalah:
Jumlah rata-rata pelanggan dalam sistem(L) adalah:
dimana di = delay dari pelanggan ke-i
Utilisasi rata-rata dari server ( ) adalah:
Utk contoh single queue kita dapatkan:
W = 1/6[(2-1)+(4-3)+(10-7)+(12-8)+(13-10.5)+(20-16)] = 2.5833
Time Average Metric Cat: sulit utk melaksanakan integrasi numerik utk evaluasi metrik performansi –
dihindari dg menggunakan kalkulasi geometrik sederhana Misalnya n(t) adalah konstan diantara waktu event dan luas di bawah kurva dp ditentukan menggunakan penjumlahan persegi Misalkan clocki menunjukan waktu clock simulasi dari event ke-i
dimana ()+ menyatakan mengambil sisi kanan diskontinuitas
Event-Scheduled Computer Simulation Pertama, identifikasi event dan state yg diperlukan utk memodelkan sistem Utk suatu sistem antrian event kedatangan, event keberangkatan, state adalah jumlah dlm sistem dan status server Buat event list berisi waktu event yang di-schedule-kan terjadi di masa depan
dlm urutan kronologis
t t1 t2 t3 …. tn Naikkan clock utk event kedepan yg akan terjadi Pada tiap waktu event, State diupdate utk event yg terjadi, sbg efek memberikan snapshot (gambaran) baru pd sistem yg dibangun Event-event kedepan di-schedule update event list (ini lebih baik drpd membangkitkan semua event disaat awal spt pd contoh dg tangan) Mudah diimplementasikan dg general purpose languages utk sistem yg kecil
Utk contoh single queue, didapatkan tf = 20
4
5/12/2014
Simulasi Antrian M/M/1
Komponen-Komponen Umum dlm Model Simulasi 1. State sistem Variabel-variabel yg digunakan utk merepresentasikan variabel state
2. Simulation Clock Variabel yg memberikan harga saat ini dari waktu yg disimulasikan
3. Event list
Model IID Exponential interarrival time dg mean 1/ IID Exponential service time dg mean 1/µ Infinite buffer Ingin mendapatkan mean customer delay dlm antrian Solusi analitis mean waiting time = / (µ - ) Contoh code dlm bahasa C:
Komponen-Komponen Umum dlm Model Simulasi
List dari waktu dan tipe dari tiap-tiap future event
4. Initialization routine Subprogram utk initialisasi model simulasi pada awal dari tiap run dengan
1) Men-set clock simulasi 2) Men-set state sistem dan counter-counter statistik 3) Schedule event pertama
5. Timing routine Subprogram yg menentukan event berikutnya (next event) dari event list dan
memajukan clock simulasi
Komponen-Komponen Model Simulasi
6. Event Routines Subprograms (satu utk tiap tipe event) utk memproses event dg Update system state Update counter-counter statistik yg mungkin Scheduled future events dari tipe yg sama (menentukan waktu event dan menambahkan ke event list)
7. Library routines Set dari subprograms utk membangkitkan random variables dan
mengumpulkan statistik
8. Report Generator Subprogram yg menghitung statistik dan menghasilkan suatu report
9. Main program Baca inputs schedules initialization, call event routines, report generator, end
of program, dll…
Common Features
Software Simulasi
Mengimplementasikan suatu discrete event simulation dg general
Secara kasar software tools utk membangun discrete event simulation dp dikategorikan kedlm empat kategori 1. General purpose languages
purpose language dipermudah dg memp. common features berikut Random number generation Harus uncorrelated, dlm prakteknya u[0,1], cepat, reproducible. Random variate generation Menggunakan bilangan random sbg input Inverse Transform method Inisialisasi simulasi Menaikkan clock Kalkulasi waktu event, meneruskan kontrol diantara routines Koleksi statistik dan analisis Output formatting Error debugging/traces
C, Pascal, FORTRAN, C++, ADA, Java, dll.
2. Event Scheduled Simulation Languages SLAM, SIMAN, SIMPAS, SIM++, JAVASIM, dll,
3. Process Oriented Simulation Languages CSIM, EZSIM, GPSS, SIMAN, SLAM, GASP, JAVASIM dll.
4. Application Oriented Simulators Opnet, Comnet III, Tangram II, ns-2, Qualnet, Jade, dll.
5
5/12/2014
Membangkitkan Bilangan dan Variabel Random
Random Number Generator
Random variables digunakan secara ekstensive pada discrete event
Random Number Generator (RNG)
simulation Perlu mampu utk membangkitkan sampel-sampel dari dari suatu
random variable x dg suatu distribusi F(x) yg dispesifikasikan
Suatu algoritma yg akan menghasilkan deretan bilangan U1, U2,
U3, …, Uk yg muncul dari sampel random variable U[0,1]
Krn keterbatasan panjang word dari komputer RNG akan selalu mengulangi deretan harga Ui setelah bbrp titik
- disebut cycle atau perioda dari RNG
Pendekatan umum utk melaksanakan ini: Pertama-tama bangkitkan sampel-sampel dari suatu uniform zero -
one random variable U [0,1] Transformasikan harga U [0,1] ke sampel-sampel dari random variable x.
Properties dari RNG yg Baik 1. Bilangan-bilangan yg dibangkitkan lolos test statistik sbg distribusi U[0,1]
Algoritma RNG adalah selalu deterministic
Orang biasa menggunakan istilah “pseudo-random number
generator”
Linear Congruential Generator (LCG) LCG didefinisikan oleh set berikut dari persamaan recursive,
Zi = (a Zi-1 + c) mod m U i = Zi / m
A chi-square test
2. Bilangan-bilangan yg dibangkitkan adalah independen Bilangan random tdk berkorelasi
3. Reproducibility Deretan yg sama akan selalu dibangkitkan utk suatu kondisi inisial yg spesifik
4. Komputasi efisien 5. Cycle time yg panjang antara repetisi dari bilangan-bilangan yg dibangkitkan 6. Memberikan hasil deretan multiple non-overlapping streams (sequences) dari bilangan-bilangan
Z0 : initial seed. a : multiplier. c: increment. M: modulus.
a, c, m dan seed Z0 semuanya integer nonnegative dan
memenuhi, a < m, c < m, Z0 <m.
Contoh LCG
Karakteristi LCG
LCG (a=5, c=3, m=16, Z0 =7)
Harga Zi pd LCG didp dg operasi mod 0 Zi (m-1), 0 Ui (m-1)/m Harga Ui akan selalu dipilih dari set
Harga m yg besar sebaiknya digunakan shg harga Ui solid dlm (0,1) Krn ada satu set terbatas dari harga Ui, LCG membangkitkan looping
cycle.
Panjang dari cycle disebut perioda p dari generator Secara umum, 0
p m. Generator memp full period jika p = m
Mean = 0.4688, Variance = 0.0885
6
5/12/2014
Generator LCG
Standar Rekomendasi RNG
Cat: Banyak pilihan parameter LCG yg mungkin yg akan memberikan hasil dlm
Utk komputer 32-bit, rekomendasi standar minimum RNG adalah
full period – tetapi tdk akan selalu memenuhi generator yg baik (mis., hargaharga tdk berkorelasi - perhatikan scatter plot dari dua LCG di bawah)
Initial Seeds
LCG (a=75, c=0, and m=231-1). Ini menghasilkan LCG :
Random Variates
Efek dari initial seed Z0 adalah utk mengambil titik awal dalam
cycle dari bilangan yang dihasilkan
Sbg contoh, LCG (a=5, c=3, m=16), jika seed Z0 =8 maka deretan yg sama
didapat mulai dari entri ke empat dlm tabel sebelumnya
Deretan-deretan dari non-overlapping random sequences dp
dibangkitkan dg initial seeds yg berbeda
Penggunaan deretan-deretan dari harga-harga yg independen Membantu memutuskan korelasi dlm simulasi Memberikan confidence intervals yg lebih akurat pada hasil
Sampel-sampel dari suatu random variabel x dg distribusi F(x) yg
dispesifikasikan dp dibangkitkan dg berbagai metoda – salah satu pendekatan adalah “the Inverse Transform technique”.
Metoda Inverse Transform memetakan harga Ui melalui F-1(Ui) utk
mendpkan harga Xi
Algoritma Inverse Transform
1) Bangkitkan Ui dari suatu RNG U[0,1] 2) Set xi = F-1(Ui).
Contoh Inverse Transform
Discrete Random Variable
Asumsi x adalah terdistribusi eksponensial dg
Jika random variable x adalah discrete random variable dg harga
F(x) = 1 – e-
x
dan
mean = 1/
Tentukan fungsi inverse transform
U = F(x) = 1 – e- x Selesaikan utk hasil-hasil x X = (-1/ ) ln(1-U) = -mean × ln(1-U)
{x1, x2,…,xn} dg x1< x2<…< xn dan densitas P{x= xi}
Maka, general inverse transform method algorithm:
1) Bangkitkan Ui dari suatu RNG U[0,1] 2) Cari j terkecil sedemikian shg Ui F(xj). 3) Set xi = xj
Exponential random variables dibangkitkan dg
1) bangkitkan Ui dari suatu RNG U[0,1] 2) Set xi = -mean × ln(1-Ui)
7
5/12/2014
Contoh Misalkan suatu random variable x dg distribusi
P(x=1)=0.2, P(x=2)=0.1, P(x=3)=0.3, P(x=4)=0.4 Algoritma utk membangkitkan random variable x adalah
1) Bangkitkan Ui dari RNG U[0,1] 2) If (Ui 0.2) then xi = 1 elseif (0.2 < Ui 0.3) then xi = 2 elseif (0.3 < Ui 0.6) then xi = 3 else xi = 4 endif
General Purpose (GP) Language C, C++, Pascal, Fortran, dll. Keuntungan utama adalah modeler biasanya sudah menguasai satu
language
Dapat diakses secara universal pada setiap komputer Efisien dlm hal waktu eksekusi krn overhead implementasi yg
lebih kecil
Pemrograman yg lebih fleksibel Tetapi keuntungan menggunakan Simulation Language biasanya
melebihi keuntungan drpd menggunakan general purpose language
Event Scheduled Simulation Language
Event Scheduled Simulation Language
Commonality dari fitur-fitur yg diperlukan utk discrete event
User menulis event routines dan main program dlm general
simulation (mis., pembangkitan random variables, event list, dll.) menyebabkan pengembangan event scheduled simulation languages (mis., Simpas, Sim++,SLAM , SIMAN, etc.) Event Scheduled Simulation Languages menyediakan framework utk event scheduled simulation Secara basic satu set library routines menyediakan common features yg diperlukan dlm discrete event simulation Misalnya random variable generation, clock, event list, dll. Languages merupakan higher level general purpose language
(mis., SIMPAS, Pascal), (SIM++, C++), (SLAM, Fortran), (SIMAN, Fortran)
purpose language utk memanggil library routines yg disediakan oleh simulation language
Pros dan Cons mengurangi lines dari code dan kesalahan dibangkitkan dg general purpose language Kecepatan sebanding dg general purpose language Memerlukan pengetahuan general purpose language dimana simulation language di-embedded-kan Masih menulis banyak code – jika banyak events tercakup
Process-Oriented Simulation Process-Oriented Simulation Suatu proses menggambarkan keseluruhan pengalaman dari
“entity” saat “mengalir” melalui sistem Bagaimana entities melalui sistem dan meninggalkan sistem
Pendekatan lebih natural drpd event -scheduling Merepresentasikan suatu sistem dg suatu jaringan dari node-node
diinterkoneksikan dg cabang-cabang Node umumnya memodelkan proses yg terjadi pada discrete
event systems Cabang-cabang memodelkan pergerakan entity
Proses umum dlm discrete event systems 1. Entity creation – bagaimana entities tiba ke system 2. Entity termination - bagaimana entities dikeluarkan dari sistem 3. Entity tranversal – pergerakan entities melalui sistem 4. Resources – substansi yg digunakan entities use atau dikonsumsi atau diduduki Dua tipe resources: 1) service – server pd antrian, 2) regular – item yg dikonsumsi entities (token pd FDDI) 5. Entity accumulation – dimana entities diantrikan 6. Branch selection – proses routing entities dlm suatu sistem 7. Entity mutiplication/reduction – memodelkan cloning dari entities atau batching dari model-model
8
5/12/2014
Process-Oriented Simulation Proses membangun model terdiri dari identifikasi entities dari sistem dan
proses-proses yg dialaminya
Model dibangun dg memilih node-node yg sesuai dg menghubungkan dg
branches
Selanjutnya parameterisasi nodes dan branches Event scheduling simulation dibangun dibawah model proses tetapi tersembunyi
Process-Oriented Simulation Contoh Single Server Queue Entities: jobs Process: creation, accumulation, resource, termination Model
dari users
Bbrp simulation languages mengimplementasikan pendekatan proses: SLAM,
SIMAN, EZSIM, CSIM, GPSS, OPNET
Cat: process oriented simulation languages umumnya memp lebih banyak node
drpd tujuh proses yg umum(mis., node utk koleksi statistik, file/attribute manipulation, dll.)
Parameters Creation: waktu creation pertama = 0, waktu antar creation = exponential random
variable dg mean =1 , attribute 1 = waktu creation Accumulation: FIFO queue, kapasitas tak terbatas (infinite) Resource: 1 server, service time = exponential dg mean = .5 Termination; berhenti setelah 6000 jobs Branches: semua branches unconditional dg zero time delay
Process –Oriented Simulation Languages
Application Oriented Simulator
Kebanyakan proses –oriented simulations memp. graphical user interface utk
Paket simulasi yg menyediakan software utk memodelkan suatu
memudahkan model building dan parameter entering
Single server queue example in EZSIM SLAM process model given on class web page process.dat CSIM Process-oriented SL based on C language. Example: csim.example on class web page
Pros dan Cons Menyediakan natural building blocks utk modeling. Memerlukan sangat sedikit atau malah tdk memerlukan pemrograman Dynamic resources allocation lebih baik Less error – lebih sedikit, automatic error checking/identification. Menyediakan struktur data yg memudahkan koleksi statistik Kurang fleksibel dlm memodelkan sistem Waktu eksekusi yg lebih lambat dg menggunakan prewritten precompiled blocks dari discrete event simulation code
Contoh NS-2 Dua node dg satu link dg antrian FIFO
domain aplikasi
Menyediakan prewritten event scheduled simulation utk
memodelkan elemen-elemen common dlm suatu aplikasi tertentu (mis., routers, segmen ethernet, token rings, dll.) Umumnya mempunyai GUI
Representasi graphic dari sistem yg disimulasikan, animasi, data analysis tools Sedikit atau tdk perlu upaya programming Reusability dari software ? Cons Konfigurasi terbatas, tidak fleksibel, akurasi model??. Mahal
Opnet, Comnet III, Tangram II, Jade, Qualnet, ns-2
Tugas (kumpul kuliah pertama setelah lebaran) 1. Consider a VoIP PBX telephone exchange at a corporation.
The PBX can connect up to 5 telephone calls simultaneously. The phone calls arrive to the PBX with a exponentially distributed amount of time between phone calls with a mean of 1 minute. The phone calls are of two types internal (80%) or external, 20%. Internal phone calls last a exponentially distributed amount of time with a mean of 3 minutes and long distance calls last a exponentially distributed amount of time with a mean of 10 minutes. The PBX can queue only 1 phone call if all 5 lines are busy, calls arriving to a full queue are dropped. (a) Determine a 90% confidence interval with a relative precision of less than 7% on the utilization of the PBX. (b) Find a 90% confidence interval on the percentage of local calls dropped. What is the relative precision? You are free to use any language you want!.
Akan dibahas pd kuliah berikutnya!
9
