| NSF Org: |
CNS Division Of Computer and Network Systems |
| Recipient: |
|
| Initial Amendment Date: | May 26, 2017 |
| Latest Amendment Date: | October 15, 2020 |
| Award Number: | 1703425 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Matt Mutka
CNS Division Of Computer and Network Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | July 1, 2017 |
| End Date: | June 30, 2021 (Estimated) |
| Total Intended Award Amount: | $473,363.00 |
| Total Awarded Amount to Date: | $473,363.00 |
| Funds Obligated to Date: |
FY 2019 = $125,941.00 FY 2020 = $129,845.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
809 S MARSHFIELD AVE M/C 551 CHICAGO IL US 60612-4305 (312)996-2862 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
851 S Morgan St Chicago IL US 60607-7042 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | CSR-Computer Systems Research |
| Primary Program Source: |
01001920DB NSF RESEARCH & RELATED ACTIVIT 01002021DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
If you have ever thought to yourself "huh, my computer didn't do that last time", you may have experienced what computer scientists call non-determinism. Today, most computer hardware executes programs in a non-deterministic fashion: a program may yield different output or behavior in different runs, given the exact same input, sometimes with disastrous consequences. Recent research enforces deterministic execution in inherently non-deterministic systems. Unfortunately, this often comes at a steep performance price. Also, until now determinism is only available for non-interactive programs. The goal of this project is to improve the efficiency of deterministic execution of concurrent programs, and to include a large class of interactive programs in the scope of deterministic execution. Longer term, the goal is to make deterministic computing a viable choice, where nondeterminism is the only option today. This would likely improve both the safety and quality of the vast number of multithreaded programs running on today's and tomorrow's multicore devices.
To bring the benefits of deterministic execution to real-world programs, this project investigates algorithms, runtime systems, operating systems and hardware support to improve the performance and applicability of determinism. The project is organized along three major thrusts: combating the clock skew in deterministic logical clocks that imposes unnecessary waiting on threads, using speculation to break the serial bottleneck that current systems impose on synchronization operations, and extending the scope of determinism to encompass interactive applications. The researchers plan to openly distribute the systems built for this project to facilitate examination by other researchers and integration with computer systems education.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
This project investigated novel techniques for, and applications of, deterministic execution of multi-threaded programs. Here, determinism means that for the same input, a program is guaranteed to produce the same output, every time. Surprisingly, this guarantee is not provided for multi-threaded programs in most of today's computing environments. Multi-threading, meanwhile, adds significant complexity to a program's behavior, but is necessary in order to take full advantage of modern, multi-core computer hardware.
Past work on deterministic multi-threading provided suitable guarantees, but at the cost of significantly slowing down the program, often to such an extent that any performance advantage provided by a multi-core computer were negated, or worse. Thus, both the overhead and the poor scalability of deterministic multi-threading were prohibitive for most use cases.
Key to deterministic multi-threading is the concept of a logical clock. This is essentially a counter that is regularly incremented at fixed points in the program, indicating the passage of time without being subject to actual timing variations that may result in nondeterminism. Having a logical clock enables the deterministic ordering of key operations between threads, which is necessary to preserve determinism. As part of this project, we developed a new logical clock with fine granularity and high efficiency, both crucial for fast deterministic multi-threading. Past work has demonstrated fine granularity, or high efficiency, but not the combination of the two.
The project also explored extending the definition of deterministic execution, to find other compelling applications of the technology developed. Among these, a particulary promising application is high-frequency background polling. Today, if an application needs to frequently check for some condition, such as externally triggered changes to values in memory, the only practical solution is to dedicate a full core to the task of "busy polling" for this condition: checking over and over. This is often done where very high networking or input-output performance is needed, but can be very wasteful, as it occupies an entire core whether or not any work is actually being performed.
Using our deterministic logical clock, we can efficiently (and deterministically) interleave even very frequent polling (millions of times per second) with other useful application work, eliminating the need for a dedicated core, thus significantly improving efficiency and performance. This, in turn, reduces both the amount of energy needed for a given task, and the time needed to perform it, in turn reducing equipment needs. While we did not foresee this particular application at the outset of the project, we anticipate that this contribution will become at least as important as deterministic multi-threading itself.
Last Modified: 07/01/2021
Modified by: Jakob Eriksson
Please report errors in award information by writing to: awardsearch@nsf.gov.
