Wednesday, 13 December 2017

Session 4: Performance Modeling and Evaluation

Mean-Field Analysis of Data Flows in Wireless Sensor Networks

Authors:

Marcel C. Guenther (Imperial College London)
Jeremy T. Bradley (Imperial College London)

Abstract:

Wireless Sensor Networks (WSNs) are often used for environment monitoring, an application which requires reliable routing of messages from source to sink nodes via multi-hop networks. Prior to installing such WSNs, engineers commonly analyse the network using discrete event simulation (DES). Whilst sophisticated simulators such as Castalia and TOSSIM take into account many low-level features of WSNs, their biggest drawback is the lack of scalability. This inhibits design-time system optimisation for large or complex networks. In this paper, we discuss how Population CTMC (PCTMC) models, used in conjunction with mean-field analysis, can be used to mitigate this problem. To illustrate the potential of PCTMC models in the WSN domain, we present a PCTMC model for a failsafe, dynamic routing protocol, which we implemented in Castalia. We show that the mean-field solution for the model yields good qualitative agreement with corresponding low-level simulations, but at a fraction of the computational cost. In particular we see good agreement for average metrics describing buffer occupancy and data flow behaviour. Moreover, our PCTMC model produces good results when packets are lost due to channel interference, an important consideration for WSNs.

DOI: 10.1145/2479871.2479882

Full text: PDF

[#][]

When Spatial and Temporal Locality Collide: The Case of the Missing Cache Hits

Authors:

Mattias De Wael (Vrije Universiteit Brussel)
David Ungar (IBM T.J. Watson Research Center)
Tom Van Cutsem (Vrije Universiteit Brussel)

Abstract:

Even the simplest hardware, running the simplest programs, can behave in the strangest of ways. Tracking down the cause of a performance anomaly without the complete hardware reference of a processor is a prime example of black-box architectural exploration. When doubling the work of a simple benchmark program, that was run on a single core of Tilera’s TILEPro64 processor, did not double the number of consumed cycles, a mystery was unveiled. After ruling out different levels of optimization for the two programs, a cycle-accurate simulation attributed the sub-optimal performance to an abnormally high number of L1 data cache misses. Further investigation showed that the processor stalled on every Read-After-Write instruction sequence when the following two conditions were met: 1) there are 0 or 1 instructions between the write and the read instruction and 2) the read and the write instructions target distinct memory locations that share an L1 cache line. We call this performance pitfall a RAW hiccup. We describe two countermeasures, memory padding and the explicit introduction of pipeline bubbles, that sidestep the RAW hiccup.

This experience paper serves as a useful troubleshooting guide for uncovering anomalous performance issues when the hardware design under study is unavailable.

DOI: 10.1145/2479871.2479883

Full text: PDF

[#][]

On Load Balancing: A Mix-Aware Algorithm for Heterogeneous Systems

Authors:

Sebastiano Spicuglia (University of Lugano)
Mathias Björkqvist (IBM Research Zurich Lab)
Lydia Y. Chen (IBM Research Zurich Lab)
Giuseppe Serazzi (Politecnico di Milano)
Walter Binder (University of Lugano)
Evgenia Smirni (College of William and Mary)

Abstract:

Today’s web services are commonly hosted on clusters of servers that are often located within computing clouds, whose computational and storage resources can be highly heterogeneous. The workload served typically exhibits disparate computation patterns (e.g., CPU-intensive or IO-intensive), that fluctuate both in terms of volume and mix. The system heterogeneity together with workload diversity further exacerbates the challenge of effective distribution of load within a computing cloud. This paper presents a novel, mix-aware load-balancing algorithm, which aims to distribute requests sent by multiple applications in heterogeneous servers such that the application response times are minimized and system resources (e.g., CPU and IO) are equally utilized. To this end, the presented algorithm tries to not only balance the total number of requests seen by each server, but also to shape the requests received by each server into a certain “mix", that is analytically shown to be optimal for response time minimization. Our experimental results— based both on simulation and on a prototype implementation— show that the mix-aware algorithm achieves robust performance in most workload mixes as well as a consistent performance improvement in comparison with one of the most robust load-balancing schemes of the Apache server.

DOI: 10.1145/2479871.2479884

Full text: PDF

[#][]