Kunal Agrawal

Kunal Agrawal

Auto-generated profile, based on publicly available information

Kunal Agrawal

Washington University in St. Louis, St. Louis, USA

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 June 2017 in Real-Time Systems
Verified
Journal Article
Closed access
PDF file
JLJing Li
Jing Li
DFDavid Ferry
David Ferry
SAShaurya Ahuja
Shaurya Ahuja
KAKunal Agrawal
Kunal Agrawal
CGChristopher Gill
Christopher Gill
CLChenyang Lu
Chenyang Lu

28 November 2017 in IEEE Transactions on Parallel and Distributed Systems
Verified
Journal Article
Open access
SDSon Ngoc Dinh
Son Ngoc Dinh
JLJing Li
Jing Li
KAKunal Agrawal
Kunal Agrawal
CGChris Gill
Chris Gill
CLChenyang Lu
Chenyang Lu
In recent years, there has been significant interest in developing real-time schedulers for parallel tasks. Most of that research has concentrated on idealized task models where tasks do not access any shared resources protected with locks. In this paper, we consider the problem of scheduling parallel tasks which experience contention due to shared resources. In particular, we provide a schedulability test for federated scheduling by deriving blocking time analyses for parallel tasks that access shared resources protected by FIFO-ordered and priority-ordered spin locks. Our numerical evaluation on randomly generated task sets indicates that priority-ordered locks generally provide better schedulability results than FIFO-ordered locks. We also incorporated both FIFO-ordered and priority-ordered spin lock implementations into a federated scheduling platform, which is able to schedule parallel tasks written with OpenMP. Via empirical evaluations, we found that priority-ordered locks also have better performance than FIFO-ordered locks in practice.

13 March 2023 in Real-Time Systems
Verified
Journal Article
Open access
PDF file
TATarek Abdelzaher
Tarek Abdelzaher
KAKunal Agrawal
Kunal Agrawal
SBSanjoy Baruah
Sanjoy Baruah
ABAlan Burns
Alan Burns
RDRobert I. Davis
Robert I. Davis
YHYigong Hu
Yigong Hu
This paper introduces and evaluates a general construct for trading off accuracy and overall execution duration in classification-based machine perception problems—namely, the generalized IDK classifier cascade. The aim is to select the optimal sequence of classifiers required to minimize the expected (i.e. average) execution duration needed to achieve successful classification, subject to a constraint on quality, and optionally a latency constraint on the worst-case execution duration. An IDK classifier is a software component that attempts to categorize each input provided to it into one of a fixed set of classes, returning “I Don’t Know” (IDK) if it is unable to do so with the required level of confidence. An ensemble of several different IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness (i.e. the probability of successful classification) and timeliness (i.e. execution duration). A model for representing such characteristics is defined, and a method is proposed for determining the values of the model parameters for a given ensemble of IDK classifiers. Optimal algorithms are developed for sequentially ordering IDK classifiers into an IDK cascade, such that the expected duration to successfully classify an input is minimized, optionally subject to a latency constraint on the worst-case overall execution duration of the IDK cascade. The entire methodology is applied to two real-world case studies. In contrast to prior work, the methodology developed in this paper caters for arbitrary dependences between the probabilities of successful classification for different IDK classifiers. Effective practical solutions are developed considering both single and multiple processors.

1 August 2014
Verified
Conference Paper
Open access
JLJing Li
Jing Li
KAKunal Agrawal
Kunal Agrawal
CGChristopher Gill
Christopher Gill
CLChenyang Lu
Chenyang Lu
Federated scheduling is a strategy to schedule parallel real-time tasks: It allocates a dedicated cluster of cores to each high-utilization task (utilization ≥ 1); It uses a multiprocessor scheduling algorithm to schedule and execute all low-utilization tasks sequentially, on a shared cluster of the remaining cores. Prior work has shown that federated scheduling has the best known capacity augmentation bound of 2 for parallel tasks with implicit deadlines. In this paper, we explore the soft real-time performance of federated scheduling and address average-case workloads instead of worst-case ones. In particular, we consider stochastic tasks - tasks for which execution time and critical-path length are random variables. In this case, we use bounded expected tardiness as the schedulability criterion. We define a stochastic capacity augmentation bound and prove that federated scheduling algorithms guarantee the same bound of 2 for stochastic tasks. We present three federated mapping algorithms with different complexities for core allocation. All of them guarantee bounded expected tardiness and provide the same capacity augmentation bound. In practice, however, we expect them to provide different performance, both in terms of the task sets they can schedule and the actual tardiness they guarantee. Therefore, we present numerical evaluations using randomly generated task sets to examine the practical differences between the three algorithms.

2 January 2018
Verified
Book Chapter
Open access
KAKunal Agrawal
Kunal Agrawal
JDJoseph Devietti
Joseph Devietti
JFJeremy T. Fineman
Jeremy T. Fineman
ILI-Ting Angelina Lee
I-Ting Angelina Lee
RURobert Utterback
Robert Utterback
CXChangming Xu
Changming Xu
A program is said to have a determinacy race if logically parallel parts of a program access the same memory location and one of the accesses is a write. These races are generally bugs in the program since they lead to non-deterministic program behavior — different schedules of the program can lead to different results. Most prior work on detecting these races focuses on a subclass of programs with series-parallel or nested parallelism. This paper presents a race-detection algorithm for detecting races in a more general class of programs, namely programs that include arbitrary ordering constraints in additional to the series-parallel constructs. The algorithm performs a serial execution of the program, augmented to detect races, in O(T1 + k2) time, where T1 is the sequential running time of the original program and k is the number of non series-parallel constraints. The main technical novelty of this paper is a new data structure, R-Sketch, for answering reachability queries in nearly series-parallel (SP) directed acyclic graphs (DAGs). Given as input a graph comprising an n-node series parallel graph and k additional non-SP edges, the total construction time of the data structure is O(n + k2), and each reachability query can be answered in O(1) time. The data structure is traversally incremental, meaning that it supports the insertion of nodes/edges, but only as they are discovered through a graph traversal.

29 March 2020 in Real-Time Systems
Verified
Journal Article
Open access
PDF file
KAKunal Agrawal
Kunal Agrawal
SBSanjoy Baruah
Sanjoy Baruah
PEPontus Ekberg
Pontus Ekberg
JLJing Li
Jing Li
In this work we consider a measurement-based model for parallel real-time tasks represented by the work and span parameters of directed acyclic graphs, with different bounds for nominal and overload scenarios. We address the corresponding real-time scheduling problem and propose an optimal scheduling strategy with a derived tight bound on the maximum response time of a task.