C436 Performance Analysis - SourceForge

C436 Performance Analysis - SourceForge

Performance Evaluation with Java Modelling Tools Giuliano Casale Department of Computing Imperial College London, UK Joint work with: Giuseppe Serazzi (Politecnico di Milano, Italy) Lulai Zhu (Imperial College London, UK) Outline

Introduction Activity 1: getting started Activity 2: load balancing Activity 3: parameter sweeping Activity 4: capacity constraints Activity 5: workflows & fork-join Please download the latest JMT (v1.0.2) here: http://jmt.sf.net/Download.html 2 Introduction

Java Modelling Tools Simulation and analysis of queueing networks. Project started in 2002 at Politecnico di Milano, since 2010 co-developed at Imperial. JMT is open source: GPL v2, Medium-size project: ~1,000 classes JAR, source code and maven build files (pom.xml) http://jmt.sourceforge.net/Download.html Good diffusion (59k downloads, mostly from the US)

Community interaction mainly through Bug reports Feature requests Templates 4 Supported models Queueing Systems Queueing Networks (QN) Product-form Extended (fork/join, blocking, priorities, )

Petri Nets (PN) Stochastic Petri Nets (SPN) Generalized Stochastic Petri Nets (GSPN) Coloured Petri Nets (CPN) Queueing Petri Nets (QPNs) 5 Who uses JMT?

JMT is for PE practice, teaching, and research Several university courses worldwide (tell us!) Supporting materials available on website 6 JMT Start Screen

Simulator 7 JSIMgraph: QN & PN simulation 8 Templates 9

JSIMwiz: wizard-based user interface 10 JSIMengine: discrete-event simulator Simulation components defined by 3 sections external arrivals (open class)

component sections queueing station Discrete-event simulation of section messaging serve admit

route complete 11 JSIMengine: JMT architecture (also stores results) CLI / XML GUI


XSLT JSIMgraph XML XML Status Status Update Update

JSIMengine 12 JMVA: analytical solver Analysis of product-form queueing networks Several exact and approximate algorithms Exact MVA Reiser & Lavenberg O(NR) Load-dependent O(N2R)

Normalizing constant RECAL CoMoM O(NM) O(NlogN) Approximate MVA O(1)

Chow Bard-Schweitzer AQL Linearizer De Souza-Muntz N: jobs

M: stations R: classes 13 JMVA: model parameterization 14 JMVA: solutions Choice of solution algorithm

15 JABA: bottleneck identification bottlenecks Common saturation sector Fraction of class 2 jobs that saturate two resources concurrently

16 JABA: bottleneck identification 3-class model Service demands of class 2 bottlenecks Service demands of class 1 17

JMCH: Markov chain animation 18 JWAT: workload characterization Column-Oriented Log File Specify Format Data Format

Templates Load Data G.Casale G.Serazzi 19 JWAT: workload characterization Scatter plots c=std. dev. /mean

Histogram Hyper-Exp (c >1) 20 Activity 1: getting started Hands-on activity: M/M/1

Arrival rate: =0.5 job/s (Exponential) Service rate: =1.00 job/s (Exponential) Goal: verify M=>M property 22 Class definition Open, closed, and mixed workloads Priorities and reference stations Reference station for closed class

Reference station for open class Reference stations used for system metrics Visits at node = TPUTnode/TPUTref ref is the reference station 23

Arrival distribution Time-Varying Peaks of User Activity Will the system sustain the load? High Performance Sun Mon

Tue Wed Thu 24 Queue section Non-preemptive scheduling: FCFS, LCFS, RAND, SJF, LJF, SEPT, LEPT, HOL (FCFS priority) Preemptive scheduling: PS, GPS, DPS

Buffer size 25 Service section number of servers exponential rate = 0.5 26

Service time distribution External trace Service time 27 Perf. Indices 19 types of performance indices Utilization, residence time, response time Throughput, firing rates, drop rates,

Granularity: system, station, class, mode, sink 28 Sim. Results performance indices confidence interval transient duration

the number of samples needed is greater than the max allowed actual sim. parameters default values of parameters 29

Statistical analysis Automated (overridable) simulation stop maximum relative error confidence level 30 traditional control parameters

30 Transient filtering Intelligent filtering of simulation data R5 heuristics, spectral analysis, MSER-5 rule, ... [Spratt, M.S. Thesis, 1998] Transient

[Pawlikowski, CSUR, 1990] (Steady State) [Heidelberger&Welch, CACM, 1981] 31 Detailed statistical results Response time percentiles, buffer overflow probability, departure process moments,

32 Loggers Simulation events can be traced in CSV files logger logger global.csv

job id (same throughout simulation) job class 33 Activity 2: Load balancing Routing section or . Probabilistic routing

State-dependent routing: JSQ, SRT, LU, FS Load-dependent probabilistic routing 35 router node Router node also allows to specify routing Applies policy across multiple input queues Same policies as routing section 36

Hands-on activity: load balancing We add two queues to the M/M/1 model. Goal: compare round-robin and probabilistic load-balancing 37 Blocking after service station with finite capacity

selection of the BAS policy max number of requests in the station BAS policy: requests are blocked in the sender station when the max capacity of the receiver is reached

38 Activity 3: Parameter sweeping Hands-on activity: bottleneck switch Analysis of bottleneck switch Measure: Number of Customers Demands: Queue 1: 10 , 5; Queue 2: 5 , 9 40

What-If analysis Perform repeated executions automatically 10 JSIM invocations 41 JMVA: What-If Common

Saturation Sector system 0.0181 job/ms system 5.5 ms class 1 Common Saturation

Sector Throughput equiload class 2 class 2 0.48 class 1

Response times 42 Activity 4: Capacity constraints FCR definition Thread limits via finite capacity regions (FCRs)

step 1 select the components of the FCR step 2 set the FCR region with constrained number of customers queue

drop 44 FCR parameters Capacity constraints: total, per-class, per-group Memory constraints: jobs have sizes and must fit Global job capacity

Global memory capacity Memory Capacity max number of requests per class in the FCR Job Size drop the requests when the region capacity is saturated

45 FCR groups and indices Group-specific constraints (i.e., for subset of classes) Dedicated performance indices

Support for PN elements Places and transitions Queueing Petri nets 47 PN sections & modes JMT design paradigm extends to PN elements Mode: a rule to activate and fire a transition

48 Hand-on activity: FCRs vs QPNs Arrival rate: =0.99 job/s Service rate: =1.00 job/s Goal: restrict max 1 job inside queue 49 Activity 5:

Workflows & fork-join Class-switching A job can change its class during the simulation Workflows, re-entrant lines, track path-wise perf., Example: re-entrant line 51 Fork-Join elements

Jobs split into tasks carrying id of the parent job Support for: nested fork-joins multiple join points finite capacity between fork-join advanced policies (e.g., quorum) JMT can compute Response time at Sink 2 only

52 Advanced fork Branch prob.: randomize no. tasks and output links Random subset: choose n-out-of-k output links Class Switch: assign new class to forked tasks 53 Advanced join Quorum: wait a subset of tasks (of the same job)

Guard: like quorum but requires given class mix Scaler: join then fork again 54 Semaphore Block first N tasks forked from the same job Upon arrival of the Nth, unblock and let the other pass 55

Case Study: YARN Capacity Scheduler YARN Yet Another Resource Negotiator 56 Case Study: YARN Capacity Scheduler Detailed model using QPN Nested FCRs (JobQueue, MapQueue, RedQueue) 14.13% error in trace-driven simulation [D. Ardagna et al., ICA3PP16]

57 Case Study: YARN Capacity Scheduler Simplified model using QN Class switching between Map tasks and Reduce tasks 58 Conclusion

Coming Soon (>= version 1.0.3) Customer impatience Ability to parallelize JMT on multiple cores Collect samples or run what-ifs in parallel Internal simulation remains single-threaded New load-balancing policies Power of k choices SITA

TreeMVA in JMVA for sparse networks Tutorial supported by the European Unions Horizon 2020 research and innovation programme under grant agreement No. 644869.60

Recently Viewed Presentations

  • Idealism - Michael Johnson

    Idealism - Michael Johnson

    Indirect Realism. Views of this general form are called "indirect realism." What you directly see are mental entities (for example, ideas). You only indirectly see the real things that the ideas represent.
  • Knife Safety

    Knife Safety

    More accidents happen when using a dull knife because it may require more force. ... Serrated bread knife. Chef's Knife. Largest knife in the kitchen. Usually 8 - 10" long. Should feel comfortable and balanced in your hand. Should have...
  • Introduction to BLDC Motor Control - RenesasRulz

    Introduction to BLDC Motor Control - RenesasRulz

    ID 610C: Introduction to BLDC Motor Control Avnet Jim Carver Technical Director, Advanced Architectures 12 October 2010 Version 1.0 * The Hall sensor, named after the man who discovered the effect, create very low level changes in voltage in proportion...
  • Towards the Development of 2014 - 2019 Strategic Plans

    Towards the Development of 2014 - 2019 Strategic Plans

    Investment Function of the SHRA could be outsourced by the SHRA to the consolidated DFI until the new legislative framework is put in place. Consolidated entity can be converted or transferred to the GBE once the new entity is established...
  • Prática de Programação Assembly 8086

    Prática de Programação Assembly 8086

    Lucida Sans Unicode Arial Wingdings 3 Verdana Wingdings 2 Calibri Concurso 1_Concurso 2_Concurso 3_Concurso 4_Concurso 5_Concurso 6_Concurso 7_Concurso Prática de Programação Assembly 8086 Modelo de Programação Modelo de Programação Endereçamento Modos de Endereçamento de Dados Conjunto de Instruções - Resumo...
  • Module 1: Bankruptcy Overview Pro Bono Bankruptcy Training

    Module 1: Bankruptcy Overview Pro Bono Bankruptcy Training

    In signing the petition, an attorney for an individual debtor who has primarily consumer debts certifies that the attorney has advised the debtor that he or she may proceed under chapter 7, 11, 12, or 13, and has explained the...
  • Presentazione di PowerPoint - unipv

    Presentazione di PowerPoint - unipv

    Platelet Microparticles Platelet microparticles, released from activated platelets, contain most of the platelet adhesive molecules and proinflammatory factors, and cause a variety of inflammatory reactions, as do activated platelets.
  • Apresentação do PowerPoint - NERE

    Apresentação do PowerPoint - NERE

    Mesa 2. Alentejo mais atrativo para investir e viver: testemunhos. Lígia Várzea - Diretora da área de Comunicação e Relações Públicas da