1 Citation (Scopus)

Abstract

Compiling concurrent programs to run on a sequential processor presents a difficult tradeoff between execution time and size of generated code. On one hand, the process-based approach to compilation generates reasonable sized code but incurs significant execution overhead due to concurrency. On the other hand, the automata-based approach incurs a much smaller execution overhead but can result in code that is several orders of magnitude larger. This paper proposes a way of combining the two approaches so that the performance of the automata-based approach can be achieved without suffering the code size increase due to it. The key insight is that the best of the two approaches can be achieved by using symbolic execution (similar to the automata-based approach) to generate code for the commonly executed paths (referred to as fast paths) and using the process-based approach to generate code for the rest of the program. We demonstrate the effectiveness of this approach by implementing our techniques in the ESP compiler and applying them to a set of filter programs and to VMMC network firmware.

Original languageEnglish (US)
Pages (from-to)189-200
Number of pages12
JournalParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
StatePublished - Dec 27 2004
EventProceedings - 13th International Conference on Parallel Architectures and Compilation Techniques (PACT 2004) - Antibes Juan-les-Pins, France
Duration: Sep 29 2004Oct 3 2004

Fingerprint

Firmware
Concurrent
Path
Automata
Symbolic Execution
Compilation
Concurrency
Compiler
Execution Time
Trade-offs
Filter
Demonstrate

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Cite this

@article{c24cad4a516e491aae31e97cf3bfc6b1,
title = "Fast paths in concurrent programs",
abstract = "Compiling concurrent programs to run on a sequential processor presents a difficult tradeoff between execution time and size of generated code. On one hand, the process-based approach to compilation generates reasonable sized code but incurs significant execution overhead due to concurrency. On the other hand, the automata-based approach incurs a much smaller execution overhead but can result in code that is several orders of magnitude larger. This paper proposes a way of combining the two approaches so that the performance of the automata-based approach can be achieved without suffering the code size increase due to it. The key insight is that the best of the two approaches can be achieved by using symbolic execution (similar to the automata-based approach) to generate code for the commonly executed paths (referred to as fast paths) and using the process-based approach to generate code for the rest of the program. We demonstrate the effectiveness of this approach by implementing our techniques in the ESP compiler and applying them to a set of filter programs and to VMMC network firmware.",
author = "Wen Xu and Sanjeev Kumar and Kai Li",
year = "2004",
month = "12",
day = "27",
language = "English (US)",
pages = "189--200",
journal = "Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT",
issn = "1089-795X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

Fast paths in concurrent programs. / Xu, Wen; Kumar, Sanjeev; Li, Kai.

In: Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT, 27.12.2004, p. 189-200.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Fast paths in concurrent programs

AU - Xu, Wen

AU - Kumar, Sanjeev

AU - Li, Kai

PY - 2004/12/27

Y1 - 2004/12/27

N2 - Compiling concurrent programs to run on a sequential processor presents a difficult tradeoff between execution time and size of generated code. On one hand, the process-based approach to compilation generates reasonable sized code but incurs significant execution overhead due to concurrency. On the other hand, the automata-based approach incurs a much smaller execution overhead but can result in code that is several orders of magnitude larger. This paper proposes a way of combining the two approaches so that the performance of the automata-based approach can be achieved without suffering the code size increase due to it. The key insight is that the best of the two approaches can be achieved by using symbolic execution (similar to the automata-based approach) to generate code for the commonly executed paths (referred to as fast paths) and using the process-based approach to generate code for the rest of the program. We demonstrate the effectiveness of this approach by implementing our techniques in the ESP compiler and applying them to a set of filter programs and to VMMC network firmware.

AB - Compiling concurrent programs to run on a sequential processor presents a difficult tradeoff between execution time and size of generated code. On one hand, the process-based approach to compilation generates reasonable sized code but incurs significant execution overhead due to concurrency. On the other hand, the automata-based approach incurs a much smaller execution overhead but can result in code that is several orders of magnitude larger. This paper proposes a way of combining the two approaches so that the performance of the automata-based approach can be achieved without suffering the code size increase due to it. The key insight is that the best of the two approaches can be achieved by using symbolic execution (similar to the automata-based approach) to generate code for the commonly executed paths (referred to as fast paths) and using the process-based approach to generate code for the rest of the program. We demonstrate the effectiveness of this approach by implementing our techniques in the ESP compiler and applying them to a set of filter programs and to VMMC network firmware.

UR - http://www.scopus.com/inward/record.url?scp=10444277207&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=10444277207&partnerID=8YFLogxK

M3 - Conference article

SP - 189

EP - 200

JO - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT

JF - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT

SN - 1089-795X

ER -