Publications

2023

1. Migration narratives in Northern Triangle, Mexican and US media from 1999 to 2019 Hinck, Robert S., Utterback, Robert, Kitsch, Sara R., and Wenzel, Sarah International Migration 2023

   Abstract This study conceptualizes the mediated discussions of migration in Central America as narratives, arguing for the need to examine the broader contours of policy-related migration reporting across time. Using machine learning and text mining analyses, combined with qualitative narrative analysis, the study examines 53,441 news articles from 17 US, Mexican and Northern Triangle media outlets from 1999 to 2019, tracing and critiquing the shifts in coverage. Findings suggest that all three media systems generally align in their depiction of the scene, key agents and acts regarding migration; however, US narratives increasingly diverge from Northern Triangle and Mexican narratives regarding the purpose and instruments by which migration occurs, with US value claims narrowing over time emphasizing border security. This narrative trajectory within US media ignores migrants’ determination and underlining rationales for migration, pushing them to take increasingly dangerous means to migrate to the USA and exacerbating the situation for all parties.

2021

1. Transforming Media Narratives on Migration: Narrative Divergence within Northern Triangle, Mexican, and US News Reporting on Migration from 1999-2019 Hinck, R. S., Kitsch, S. R., Utterback, R., and Wenzel, S. Paper presented at the 2021 National Communication Association Annual Conference, Seattle, WA 2021
   2021
2. Mexican and Northern Triangle Perspectives on Migration: Identifying and Assessing Strategic Narrative Alignment Media Ecology & Strategic Analysis (MESA) Group (Skye Cooley, Robert Hinck, Asya Cooley, Sara Kitsch, Robert Utterback, Jared Johnson) Prepared for the U.S. Department of Homeland Security
   2021

2019

1. Jammu and Kashmir Reach Back: Media Analysis of Extremist Activities in Indian and Pakistani News Cooley, Skye, Hinck, Robert, and Utterback, Robert A Media Ecology & Strategic Analysis (MESA) Group Report
   2019
2. Efficient Race Detection with Futures Utterback, Robert, Agrawal, Kunal, Fineman, Jeremy, and Lee, I-Ting Angelina In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming 2019 [PDF]

   This paper addresses the problem of provably efficient and practically good on-the-fly determinacy race detection in task parallel programs that use futures. Prior works on determinacy race detection have mostly focused on either task parallel programs that follow a series-parallel dependence structure or ones with unrestricted use of futures that generate arbitrary dependences. In this work, we consider a restricted use of futures and show that we can detect races more efficiently than with general use of futures. Specifically, we present two algorithms: MultiBags and MultiBags+. MultiBags targets programs that use futures in a restricted fashion and runs in time O(T1α(m, n)), where T1 is the sequential running time of the program, α is the inverse Ackermann’s function, m is the total number of memory accesses, n is the dynamic count of places at which parallelism is created. Since α is a very slowly growing function (upper bounded by 4 for all practical purposes), it can be treated as a close-to-constant overhead. MultiBags+ is an extension of MultiBags that target programs with general use of futures. It runs in time O((T1 + k2)α(m, n)) where T1, α, m and n are defined as before, and k is the number of future operations in the computation. We implemented both algorithms and empirically demonstrate their efficiency.

3. Processor-Oblivious Record and Replay Utterback, Robert, Agrawal, Kunal, Lee, I-Ting Angelina, and Kulkarni, Milind ACM Trans. Parallel Comput. 2019

   Record-and-replay systems are useful tools for debugging non-deterministic parallel programs by first recording an execution and then replaying that execution to produce the same access pattern. Existing record-and-replay systems generally target thread-based execution models, and record the behaviors and interleavings of individual threads. Dynamic multithreaded languages and libraries, such as the Cilk family, OpenMP, TBB, and the like, do not have a notion of threads. Instead, these languages provide a processor-oblivious model of programming, where programs expose task parallelism using high-level constructs such as spawn/sync without regard to the number of threads/cores available to run the program. Thread-based record-and-replay would violate the processor-oblivious nature of these programs, as they incorporate the number of threads into the recorded information, constraining the replayed execution to the same number of threads. In this article, we present a processor-oblivious record-and-replay scheme for dynamic multithreaded languages where record and replay can use different number of processors and both are scheduled using work stealing. We provide theoretical guarantees for our record and replay scheme—namely that record is optimal for programs with one lock and replay is near-optimal for all cases. In addition, we implemented this scheme in the Cilk Plus runtime system and our evaluation indicates that processor-obliviousness does not cause substantial overheads.

2018

1. Race Detection and Reachability in Nearly Series-Parallel DAGs Agrawal, Kunal, Devietti, Joseph, Fineman, Jeremy T., Lee, I-Ting Angelina, Utterback, Robert, and Xu, Changming In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms 2018 [PDF]

   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.

2017

1. Processor-Oblivious Record and Replay Utterback, Robert, Agrawal, Kunal, Lee, I-Ting Angelina, and Kulkarni, Milind In Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming 2017 [PDF]

   Record-and-replay systems are useful tools for debugging non-deterministic parallel programs by first recording an execution and then replaying that execution to produce the same access pattern. Existing record-and-replay systems generally target thread-based execution models, and record the behaviors and interleavings of individual threads. Dynamic multithreaded languages and libraries, such as the Cilk family, OpenMP, TBB, etc., do not have a notion of threads. Instead, these languages provide a processor-oblivious model of programming, where programs expose task-parallelism using high-level constructs such as spawn/sync without regard to the number of threads/cores available to run the program. Thread-based record-and-replay would violate the processor-oblivious nature of these programs, as they incorporate the number of threads into the recorded information, constraining the replayed execution to the same number of threads. In this paper, we present a processor-oblivious record-and-replay scheme for such languages where record and replay can use different number of processors and both are scheduled using work stealing. We provide theoretical guarantees for our record and replay scheme — namely that record is optimal for programs with one lock and replay is near-optimal for all cases. In addition, we implemented this scheme in the Cilk Plus runtime system and our evaluation indicates that processor-obliviousness does not cause substantial overheads.

2016

1. Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs Utterback, Robert, Agrawal, Kunal, Fineman, Jeremy T., and Lee, I-Ting Angelina In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures 2016 [PDF]

   If a parallel program has determinacy race(s), different schedules can result in memory accesses that observe different values — various race-detection tools have been designed to find such bugs. A key component of race detectors is an algorithm for series-parallel (SP) maintenance, which identifies whether two accesses are logically parallel. This paper describes an asymptotically optimal algorithm, called WSP-Order, for performing SP maintenance in programs with fork-join (or nested) parallelism. Given a fork-join program with T1 work and T∞ span, WSP-Order executes it while also maintaining SP relationships in O(T1/P + T∞) time on P processors, which is asymptotically optimal. At the heart of WSP-Order is a work-stealing scheduler designed specifically for SP maintenance. We also implemented C-RACER, a race-detector based on WSP-Order within the Cilk Plus runtime system, and evaluated its performance on five benchmarks. Empirical results demonstrate that when run sequentially, it performs almost as well as previous best sequential race detectors. More importantly, when run in parallel, it achieves almost as much speedup as the original program without race-detection.

2014

1. Provably Good Scheduling for Parallel Programs That Use Data Structures Through Implicit Batching Agrawal, Kunal, Fineman, Jeremy T., Lu, Kefu, Sheridan, Brendan, Sukha, Jim, and Utterback, Robert In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures 2014 [PDF]

   Although concurrent data structures are commonly used in practice on shared-memory machines, even the most efficient concurrent structures often lack performance theorems guaranteeing linear speedup for the enclosing parallel program. Moreover, efficient concurrent data structures are difficult to design. In contrast, parallel batched data structures do provide provable performance guarantees, since processing a batch in parallel is easier than dealing with the arbitrary asynchrony of concurrent accesses. They can limit programmability, however, since restructuring a parallel program to use batched data structure instead of concurrent data structure can often be difficult or even infeasible. This paper presents BATCHER, a scheduler that achieves the best of both worlds through the idea of implicit batching, and a corresponding general performance theorem. BATCHER takes as input (1) a dynamically multithreaded program that makes arbitrary parallel accesses to an abstract data type, and (2) an implementation of the abstract data type as a batched data structure that need not cope with concurrent accesses. BATCHER extends a randomized work-stealing scheduler and guarantees probably good performance to parallel algorithms that use these data structures. In particular, suppose a parallel algorithm has (i)T_1(i/) work, (I)T_∞(I/) span, and (I)n(I/) data-structure operations. Let (I)W(n)(I/) be the total work of data-structure operations and let (I)s(n)(I/) be the span of a size-(I)P(I/) batch. Then BATCHER executes the program in (I)O((T_1+W(n) + n s(n))/P+ s(n) T_∞)(I/) expected time on (I)P(I/) processors. For higher-cost data structures like search trees and large enough (I)n(I/), this bound becomes (I)(T_1+n\lg n)/P + T_∞lg n)(I/) provably matching the work of a sequential search tree but with nearly linear speedup, even though the data structure is accessed concurrently. The BATCHER runtime bound also readily extends to data structures with amortized bounds.