Search

Capture–recapture (CRC) surveys are used to estimate the size of a population whose members cannot be enumerated directly. CRC surveys have been used to estimate the number of Coronavirus Disease 2019 (COVID-19) infections, people who use drugs, sex workers, conflict casualties, and trafficking victims. When k-capture samples are obtained, counts of unit captures in subsets of samples are represented naturally by a 2k contingency table in which one element—the number of individuals appearing in none of the samples—remains unobserved. In the absence of additional assumptions, the population size is not identifiable (i.e., point identified). Stringent assumptions about the dependence between samples are often used to achieve point identification. However, real-world CRC surveys often use convenience samples in which the assumed dependence cannot be guaranteed, and population size estimates under these assumptions may lack empirical credibility. In this work, we apply the theory of partial identification to show that weak assumptions or qualitative knowledge about the nature of dependence between samples can be used to characterize a nontrivial confidence set for the true population size. We construct confidence sets under bounds on pairwise capture probabilities using two methods: test inversion bootstrap confidence intervals and profile likelihood confidence intervals. Simulation results demonstrate well-calibrated confidence sets for each method. In an extensive real-world study, we apply the new methodology to the problem of using heterogeneous survey data to estimate the number of people who inject drugs in Brussels, Belgium.

Research on modeling and analysis of real-time computing systems has been done in two areas, model checking and real-time scheduling theory. In model checking, an expressive modeling formalism such as timed automata (TA) is used to model complex systems, but the analysis is typically very expensive due to state-space explosion. In real-time scheduling theory, the analysis techniques are highly efficient, but the models are often restrictive. In this paper, we aim to exploit the possibility of applying efficient analysis techniques rooted in real-time scheduling theory to analysis of real-time task systems modeled by timed automata with tasks (TAT). More specifically, we develop efficient techniques to analyze the feasibility of TAT-based task models (i.e., whether all tasks can meet their deadlines on single-processor) using demand bound functions (DBF), a widely used workload abstraction in real-time scheduling theory. Our proposed analysis method has a pseudo-polynomial time complexity if the number of clocks used to model each task is bounded by a constant, which is much lower than the exponential complexity of the traditional model-checking based analysis approach (also assuming the number of clocks is bounded by a constant). We apply dynamic programming techniques to implement the DBF-based analysis framework, and propose state space pruning techniques to accelerate the analysis process. Experimental results show that our DBF-based method can analyze a TAT system with 50 tasks within a few minutes, which significantly outperforms the state-of-the-art TAT-based schedulability analysis tool TIMES.

Multi-cores are becoming mainstream hardware platforms for embedded and real-time systems. To fully utilize the processing capacity of multi-cores, software should be parallelized. Recently, much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG), motivated by the parallel task structures supported by popular parallel programming frameworks such as OpenMP. The DAG-based task models in existing real-time scheduling research assume well-nested graph structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP task systems in general have more flexible structures that do not comply with those assumptions. In this article, we model the behavior of general OpenMP task systems with non-well-nested structures. The worst-case response time analysis problem for such systems is more difficult due to the flexible graph structure. As the major technical contribution, we develop two efficient algorithms to compute the worst-case response time bounds, with different trade-offs between efficiency and precision. Evaluation with both randomly generated task graphs and realistic OpenMP programs shows good performance of our approaches in terms of both precision and efficiency.

Capacity augmentation bound (CAB) is a widely used quantitative metric in theoretical analysis for directed acyclic graph (DAG) parallel real-time tasks, which reveals the key factors the schedulability of DAG tasks heavily depending on: the normalized utilization (the ratio of the total utilization to the core numbers) and the tensity (the maximum ratio of task’s longest path length to task’s deadline). However, CAB requires both factors of a schedulable task system to be capped by the same threshold. A task system with a normalized utilization slightly larger than that threshold but very small tensity, or very smaller normalized utilization but slightly larger than that threshold has good chance to be scheduled are both denied by CAB. To this end, we propose a new concept called capacity augmentation function (CAF) to better characterize the schedulability of parallel real-time tasks, which provides a more loose and different threshold for both factors. In particular, we derive a CAF-based linear-time schedulability test for real-time constrained-deadline DAG tasks under global EDF, which entirely dominates the state-of-the-art CAB-based test for constrained-deadline settings. Finally, we conduct experiments to compare the acceptance ratio of our CAF-based test with the existing schedulability tests also having linear-time complexity. The results show that CAF-based test significantly outperforms the existing linear-time schedulability test under different parameter settings.

The demand bound function (DBF) is a powerful abstraction to analyze the feasibility/schedulability of real-time tasks. Computing the DBF for expressive system models, such as graph-based tasks, is typically very expensive. In this article, we develop new techniques to drastically improve the DBF computation efficiency for a representative graph-based task model, digraph real-time tasks (DRT). First, we apply the well-known quick processor-demand analysis (QPA) technique, which was originally designed for simple sporadic tasks, to the analysis of DRT. The challenge is that existing analysis techniques of DRT have to compute the demand for each possible interval size, which is contradictory to the idea of QPA that aims to aggressively skip the computation for most interval sizes. To solve this problem, we develop a novel integer linear programming (ILP)-based analysis technique for DRT, to which we can apply QPA to significantly improve the analysis efficiency. Second, we improve the task utilization computation (a major step in DBF computation for DRT) efficiency from pseudo-polynomial complexity to polynomial complexity. Experiments show that our approach can improve the analysis efficiency by dozens of times.

OpenMP is a promising framework to develop parallel real-time software on multi-cores. Although similar to the DAG task model, OpenMP task systems are significantly more difficult to analyze due to constraints posed by OpenMP specifications. One of the most interesting features in OpenMP is the support for nested parallelism, enjoying benefits in enhancing performance transparency of parallel libraries and promoting reuse of black-box code. Previous researches on DAG task scheduling mainly restrict to only one level of parallelism. The problem whether OpenMP tasks with multiple levels of parallelism are suitable to real-time systems remains open. In this paper, we study the real-time scheduling and analysis of OpenMP task systems supporting nested parallelism. First, we show that under existing scheduling algorithms in OpenMP implementations, nested parallelism indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we propose a new scheduling algorithm and develop two sound response time bounds by considering the trade-off between simplicity and analysis precision. Experiments demonstrate the efficiency of our methods.

Utilization bound is a well-known concept in real-time scheduling theory for sequential periodic tasks, which can be used both for quantifying the performance of scheduling algorithms and as efficient schedulability tests. However, the schedulability of parallel real time task graphs depends on not only utilization, but also another parameter tensity , the ratio between the longest path length and period. In this paper, we use utilization-tensity bounds to better characterize the schedulability of parallel real-time tasks. In particular, we derive utilization-tensity bounds for parallel DAG tasks under global EDF scheduling, which facilitate significantly more precise schedulability analysis than the state-of-the-art analysis techniques based on capacity augmentation bound and response time analysis. Moreover, we apply the above results to the federated scheduling paradigm to improve the system schedulability by choosing proper scheduling strategies for tasks with different workload and structure features.

Most current real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Existing worst-case response time (WCRT) bounds (e.g., Graham's bound) derived for DAGs may be very pessimistic. No one precisely knows the gap between the WCRT bound and the actual WCRT. In this paper, we aim to derive the exact WCRT of a DAG task under the list scheduling upon multi-core platforms. We encode the WCRT analysis problem into a satisfaction modular theoretical (SMT) formulation based on insights into the list scheduling algorithm, and prove that our SMT program can solve the WCRT precisely, providing an accurate baseline to measure the tightness of the existing WCRT bounds. Experiments show that our method significantly improves the tightness of the WCRT bound, and is practically quite efficient, e.g., it can analyze DAGs with more than 40 vertices in a few seconds.

Challenging scheduling problems arise in the implementation of cyber-physical systems upon heterogeneous platforms with (serial) data offloading and (parallel) computation. In this paper, we adapt techniques from scheduling theory to model, analyze, and derive scheduling algorithms for real-time workloads on such platforms. We characterize the performance of the proposed algorithms, both analytically via the approximation ratio metric and experimentally through simulation experiments upon synthetic workloads that are justified via a case study on a CPU-GPU platform. The evaluation exposes some divergence between the analytical characterization and experimental one; recommendations that seek to balance such divergent characterizations are made regarding the choice of algorithmic approaches.

The hardness of analyzing conditional directed acyclic graph (DAG) tasks remains unknown so far. For example, previous researches asserted that the conditional DAG's volume can be solved in polynomial time. However, these researches all assume well-nested structures that are recursively composed by single-source-single-sink parallel and conditional components. For conditional DAGs in general that do not comply with this assumption, the hardness and algorithms of volume computation are still open. In this paper, we construct counterexamples to show that previous work cannot provide a safe upper bound of the conditional DAG's volume in general. Moreover, we prove that the volume computation problem for conditional DAGs is strongly $\mathcal{N}\mathcal{P}$-hard. Finally, we propose an exact algorithm for computing the conditional DAG's volume. Experiments show that our method can significantly improve the accuracy of the conditional DAG's volume estimation.

Capacity augmentation bound is a widely used quantitative metric in theoretical studies of schedulability analysis for directed acyclic graph (DAG) parallel real-time tasks, which not only quantifies the suboptimality of the scheduling algorithms, but also serves as a simple linear-time schedulability test. Earlier studies on capacity augmentation bounds of the sporadic DAG task model were either restricted to a single DAG task or a set of tasks with implicit deadlines. In this paper, we consider parallel tasks with constrained deadlines under global earliest deadline first policy. We first show that it is impossible to obtain a constant bound for our problem setting, and derive both lower and upper bounds of the capacity augmentation bound as a function with respect to the maximum ratio of task period to deadline. Our upper bound is at most 1.47 times larger than the optimal one. We conduct experiments to compare the acceptance ratio of our capacity augmentation bound with the existing schedulability test also having linear-time complexity. The results show that our capacity augmentation bound significantly outperforms the existing linear-time schedulability test under different parameter settings.

Synchronous parallel tasks are widely used in HPC for purchasing high average performance, but merely consider how to guarantee good timing predictabilities. OpenMP is a promising framework for multi-core real-time embedded systems. The synchronous OpenMP tasks are significantly more difficult to schedule and analyze due to constraints posed by OpenMP specifications. An important OpenMP feature is tied task, which must execute on the same thread during the whole life cycle. This paper designs a novel method, called group scheduling, to schedule synchronous OpenMP tasks, which divides tasks into several groups, and assigns some of them to dedicated cores, in order to isolate tied tasks. We derive a linear-time computable response time bound. Experiments with both randomly generated and realistic OpenMP tasks show that our new bound significantly outperforms the existing bound.

Existing DAG-based task models in real-time scheduling research assume well-nested structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP task systems in general have more flexible structures that do not comply with this assumption. In this paper, we model the behaviors of general OpenMP task systems with non-well-nested branching structures and study the problem of how to bound their worst-case response times (WCRT). A naive solution is to apply the established WCRT bound for DAG tasks without conditional branches to the exponentially many possible execution flows, which has exponential time complexity. In this paper, we develop a linear-time algorithm to efficiently calculate WCRT bounds for OpenMP task systems with non-well-nested branching structures. Experiments with both synthetic task graphs and realistic OpenMP programs are conducted to evaluate the performance of our method.

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are significantly more precise than the existing bound while having good scalability.

As radar sea clutter has chaotic characteristics, a prediction model can be established to predict sea clutter according to short-term predictability of chaotic time series. Therefore, this paper proposes a sea clutter amplitude prediction model based on LSTM, Stacked LSTM and Nested LSTM. This paper first obtains the best state space for sea clutter prediction according to the phase space reconstruction theory and establishes the prediction equation, then uses three networks to predict the sea clutter amplitude, and finally compares the effects of the three neural networks and analyzes the factors that affect the prediction precision. The experimental results on the IPIX radar data and P-band radar data show that, the model used in this paper has a smaller prediction error than RBF, and the prediction performance is better. The model can achieve high-precision and high-efficiency prediction of sea clutter and has verified the effectiveness of the method.

In the formal analysis of real-time systems, modeling of branching codes and modeling of intratask parallelism structures are two of the most important research topics. These two real-time properties are combined, resulting in the fork-join real-time task (FJRT) model, which extends the digraph-based task model with forking and joining semantics. We prove that the EDF schedulability problem on a preemptive uniprocessor for the FJRT model is coNP-hard in the strong sense, even if the utilization of the task system is bounded by a constant strictly less than 1. Then, we show that the problem becomes tractable with some slight structural restrictions on parallel sections, for which we propose an exact schedulability test with pseudo-polynomial time complexity. Our results thus establish a borderline between the tractable and intractable FJRT models.

Heterogeneous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of \emph{typed} scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the \emph{non-self-sustainability} problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its \emph{non-self-sustainability} problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are significantly more precise than the existing bound while having good scalability.

OpenMP is a promising framework for developing parallel real-time software on multi-cores. Although similar to the DAG task model, OpenMP task systems are significantly more difficult to analyze due to constraints posed by the OpenMP specification. An important feature in OpenMP is tied tasks, which must execute on the same thread during the whole life cycle. Although tied tasks enjoy benefits in simplicity and efficiency, it was considered to be not suitable to real-time systems due to its complex behavior. In this paper, we study the realtime scheduling and analysis of OpenMP task systems with tied tasks. First, we show that under the existing scheduling algorithms in OpenMP, tied tasks indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we proposed a new scheduling algorithm and developed two response time bounds for it, with different trade-off between simplicity and analysis precision. Experiments with both randomly generated OpenMP task systems and realistic OpenMP programs show that the response time bounds obtained by our approach for tied task systems are very close to that of untied tasks.