Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Slowdown Prediction Method to Improve Memory Aware Scheduling
University West, Department of Engineering Science, Division of Computer, Electrical and Surveying Engineering. Institutionen för data- och informationsteknik, Datorteknik (Chalmers.ORCID iD: 0000-0001-7232-0079
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Scientific and technological advances in the area of integrated circuits have allowed the performance of microprocessors to grow exponentially since the late 1960's. However, the imbalance between processor and memory bus capacity has increased in recent years. The increasing on-chip-parallelism of multi-core processors has turned the memory subsystem into a key factor for achieving high performance. When two or more processes share the memory subsystem their execution times typically increase, even at relatively low levels of memory traffic. Current research shows that a throughput increase of up to 40% is possible if the job-scheduler can minimizes the slowdown caused by memory contention in industrial multi-core systems such as high performance clusters, datacenters or clouds. In order to optimize the throughput the job-scheduler has to know how much slower the process will execute when co-scheduled on the same server as other processes. Consequently, unless the slowdown is known, or can be fairly well estimated, the scheduling becomes pure guesswork and the performance suffers. The central question addressed in this thesis is how the slowdown caused by memory traffic interference between processes executing on the same server can be predicted and to what extent. This thesis presents and evaluates a new slowdown prediction method which estimates how much longer a program will execute when co-scheduled on the same multi-core server as another program. The method measures how external memory traffic affects a program by generating different levels of synthetic memory traffic while observing the change in execution time. Based on the observations it makes a first order prediction of how much slowdown the program will experience when exposed to external memory traffic. Experimental results show that the method's predictions correlate well with the real measured slowdowns. Furthermore, it is shown that scheduling based on the new slowdown prediction method yields a higher throughput than three other techniques suggested for avoiding co-scheduling slowdowns caused by memory contention. Finally, a novel scheme is suggested to avoid some of the worst co-schedules, thus increasing the system throughput.

Place, publisher, year, edition, pages
Göteborg: Chalmers University of Technology , 2016. , p. 19
Series
Doktorsavhandlingar vid Chalmers tekniska högskola, Ny serie, ISSN 0346-718X ; 4050
Keywords [en]
Multi-core processor, slowdown aware scheduling, memory bandwidth, resource contention, last level cache, co-scheduling, performance evaluation
National Category
Computer Systems Information Systems, Social aspects
Research subject
ENGINEERING, Computer engineering
Identifiers
URN: urn:nbn:se:hv:diva-9300ISBN: 978-91-7597-369-2 (print)OAI: oai:DiVA.org:hv-9300DiVA, id: diva2:917796
Public defence
2016-04-19, EC, Hörsalsvägen 11, Chalmers, Göteborg, 10:00 (English)
Opponent
Supervisors
Available from: 2016-04-07 Created: 2016-04-07 Last updated: 2016-04-07Bibliographically approved
List of papers
1. Dual-core efficiency for engineering simulation applications
Open this publication in new window or tab >>Dual-core efficiency for engineering simulation applications
Show others...
2008 (English)In: 2008 International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2008: Las Vegas, NV; 14 July 2008 through 17 July 2008, 2008, p. 962-968Conference paper, Published paper (Refereed)
National Category
Information Systems
Research subject
Engineering, Computer engineering
Identifiers
urn:nbn:se:hv:diva-1513 (URN)978-160132084-1 (ISBN)
Available from: 2009-05-11 Created: 2009-05-11 Last updated: 2018-01-13Bibliographically approved
2. Method for Experimental Measurement of an Applications Memory Bus Usage
Open this publication in new window or tab >>Method for Experimental Measurement of an Applications Memory Bus Usage
2010 (English)In:   / [ed] Hamid Arabnia, CSREA Press , 2010Conference paper, Published paper (Refereed)
Abstract [en]

The disproportion between processor and memory bus capacities has increased constantly during the last decades. With the introduction of multi-core processors the memory bus capacity is divided between the simultaneously executing processes (cores). The memory bus capacity directly affects the number of applications that can be executed simultaneously at its full potential. Thus, against this backdrop it becomes important to estimate how the limitation of the memory bus effects the applications performance. Towards this end we introduce a method and a tool for experimental estimation of an applications memory requirement as well as the impact of sharing the memory bus has on the execution times. The tool enables black-box approximate profiling of an applications memory bus usage during execution. It executes entirely in user-space and does not require access to the application code, only the binary. 

Place, publisher, year, edition, pages
CSREA Press, 2010
Keywords
Memory, experimental measurement, Multi-core, tool, prediction
National Category
Computer Engineering
Research subject
ENGINEERING, Computer engineering
Identifiers
urn:nbn:se:hv:diva-2445 (URN)
Conference
The 2010 International Conference on Parallel and Distributed Processing Techniques and Applications
Available from: 2010-05-03 Created: 2010-05-03 Last updated: 2018-01-12Bibliographically approved
3. A methodology for estimating co-scheduling slowdowns due to memory bus contention on multicore nodes
Open this publication in new window or tab >>A methodology for estimating co-scheduling slowdowns due to memory bus contention on multicore nodes
2014 (English)In: Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2014, 2014, p. 216-223Conference paper, Published paper (Refereed)
Abstract [en]

When two or more programs are co-scheduled on the same multicore computer they might experience a slowdown due to the limited off-chip memory bandwidth. According to our measurements, this slowdown does not depend on the total bandwidth use in a simple way. One thing we observe is that a higher memory bandwidth usage will not always lead to a larger slowdown. This means that relying on bandwidth usage as input to a job scheduler might cause non-optimal scheduling of processes on multicore nodes in clusters, clouds, and grids. To guide scheduling decisions, we instead propose a slowdown based characterization approach. Real slowdowns are complex to measure due to the exponential number of experiments needed. Thus, we present a novel method for estimating the slowdown programs will experience when co-scheduled on the same computer. We evaluate the method by comparing the predictions made with real slowdown data and the often used memory bandwidth based method. This study show that a scheduler relying on slowdown based categorization makes fewer incorrect co-scheduling choices and the negative impact on program execution times is less than when using a bandwidth based categorization method.

Keywords
Cluster, cloud, multicore, memory bandwidth, co-scheduling, slowdown
National Category
Computer Sciences
Research subject
ENGINEERING, Computer engineering
Identifiers
urn:nbn:se:hv:diva-6195 (URN)10.2316/P.2014.811-027 (DOI)2-s2.0-84898422321 (Scopus ID)
Conference
12th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2014; Innsbruck; Austria; 17 February 2014 through 19 February 2014; Code 104419
Available from: 2014-05-07 Created: 2014-04-30 Last updated: 2018-01-11Bibliographically approved
4. Addressing characterization methods for memory contention aware co-scheduling
Open this publication in new window or tab >>Addressing characterization methods for memory contention aware co-scheduling
2015 (English)In: Journal of Supercomputing, ISSN 0920-8542, E-ISSN 1573-0484, Vol. 71, no 4, p. 1451-1483Article in journal (Refereed) Published
Abstract [en]

The ability to precisely predict how memory contention degrades performance when co-scheduling programs is critical for reaching high performance levels in cluster, grid and cloud environments. In this paper we present an overview and compare the performance of state-of-the-art characterization methods for memory aware (co-)scheduling. We evaluate the prediction accuracy and co-scheduling performance of four methods: one slowdown-based, two cache-contention based and one based on memory bandwidth usage. Both our regression analysis and scheduling simulations find that the slowdown based method, represented by Memgen, performs better than the other methods. The linear correlation coefficient (Formula presented.) of Memgen's prediction is 0.890. Memgen's preferred schedules reached 99.53 % of the obtainable performance on average. Also, the memory bandwidth usage method performed almost as well as the slowdown based method. Furthermore, while most prior work promote characterization based on cache miss rate we found it to be on par with random scheduling of programs and highly unreliable.

Keywords
Memory contention, Memory subsystem, Performance measurements, Co-scheduling, Slowdown based scheduling
National Category
Computer Sciences
Research subject
ENGINEERING, Computer engineering
Identifiers
urn:nbn:se:hv:diva-7664 (URN)10.1007/s11227-014-1374-8 (DOI)2-s2.0-84939948746 (Scopus ID)
Available from: 2015-06-02 Created: 2015-06-02 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Länk till fulltext

Authority records BETA

De Blanche, Andreas

Search in DiVA

By author/editor
De Blanche, Andreas
By organisation
Division of Computer, Electrical and Surveying Engineering
Computer SystemsInformation Systems, Social aspects

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 598 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf