Successful attacks against industrial control systems (ICSs) often exploit insufficient checking mechanisms. While firewalls, intrusion detection systems, and similar appliances introduce essential checks, their efficacy depends on the attackers’ ability to bypass such middleboxes. We propose a provenance solution to enable the verification of an end-to-end message delivery path and the actions performed on a message. Fast and flexible provenance verification (F2-Pro) provides cryptographically verifiable evidence that a message has originated from a legitimate source and gone through the necessary checks before reaching its destination. F2-Prorelies on lightweight cryptographic primitives and flexibly supports various communication settings and protocols encountered in ICS thanks to its transparent, bump-in-the-wire design. We provide formal definitions and cryptographically prove F2-Pro’s security. For human interaction with ICS via a field service device, F2-Profeatures a multi-factor authentication mechanism that starts the provenance chain from a human user issuing commands. We compatibility tested F2-Proon a smart power grid testbed and reported a sub-millisecond latency overhead per communication hop using a modest ARM Cortex-A15 processor.

Evaluation of highly dependable systems requires estimating the probability of a significant rare event under which the system fails to meet the requirement. To improve the estimation accuracy, advanced Monte Carlo simulation techniques such as importance sampling (IS) are commonly used. However, IS is known to misbehave under high dimension. As a result, the IS estimator can have a large relative error and underestimate the rare event probability. In this paper, we propose a novel IS method based on the idea of maximum weight minimization (MWM). Our method works by finding the sampling distribution that minimizes the maximum weight of a rare event sample. To alleviate the curse of dimensionality, we develop further heuristics based on two problem-specific structures, namely, monotonicity and symmetry. Using extensive examples from network reliability, stochastic flow analysis, cyber-security risk assessment, and fault tree analysis, we evaluate the performance of MWM, demonstrate its accuracy and scalability, and highlight applications where it outperforms state-of-the-art techniques.

We describe a platform that uses temporally integrated co-simulation of emulated devices and simulation of networks that connect them, for activities such as performance evaluation and resilience assessment. In our approach all emulated and simulated components are time-synchronized to a virtual clock. We propose and study an approach which uses compiler analysis to augment emulated code with logic for precise instruction level tracking of execution paths. This is combined with a mechanism to ascribe virtual time for each execution burst based on the sequence of executed instructions. The overhead of synchronization between emulated components and simulated components is reduced by compiler-based identification of “lookahead”, which identifies epochs of emulated execution during which a process can be predicted to act independently of any other. Through evaluations, we show that our approach enables fast and repeatable execution of co-simulated models.

In the aftermath of a disaster, the ability to reliably communicate and coordinate emergency response could make a meaningful difference in the number of lives saved or lost. However, post-disaster areas tend to have limited functioning communication network infrastructure while emergency response teams are carrying increasingly more devices, such as sensors and video transmitting equipment, which can be low-powered with limited transmission ranges. In such scenarios, unmanned aerial vehicles (UAVs) can be used as relays to connect these devices with each other. Since first responders are likely to be constantly mobile, the problem of where these UAVs are placed and how they move in response to the changing environment could have a large effect on the number of connections this UAV relay network is able to maintain. In this work, we propose DroneDR, a reinforcement learning framework for UAV positioning that uses information about connectivity requirements and user node positions to decide how to move each UAV in the network while maintaining connectivity between UAVs. The proposed approach is shown to outperform other greedy heuristics across a broad range of scenarios and demonstrates the potential in using reinforcement learning techniques to aid communication during disaster relief operations.

Network emulators enable rapid prototyping and testing of applications. In a typical emulation the execution order and process execution burst lengths are managed by the host platform's operating system, largely independent of the emulator. Timer based mechanisms are typically used, but the imprecision of timer firings introduces imprecision in the advancement of time. This leads to statistical variation in behavior which is not due to the model.

Cyber-security risk assessment includes estimation of losses possible to a system due to cyber-attacks. As there are uncertain elements to this and as we model uncertainty using probability, we seek to estimate the attack loss distribution. In particular, the tail of the distribution represents the low-probability but high-impact events. However, quantifying those events using standard Monte Carlo techniques is inefficient due to the low probability. This paper proposes a novel cyber-security risk assessment approach based on uncertain graphs, with an emphasis on modeling losses due to cyber-attacks. Under rare event realizations where the attack loss is greater than a selected threshold, we (i) derive the analytically optimal importance sampling scheme for the loss tail probability and (ii) propose an approximation to the optimal importance sampling scheme which has the assurance of bounded relative error. While the approximation scheme requires solving an NP-hard problem, we use a search procedure that becomes more efficient as the attack loss threshold increases. A case study on a medium-sized network demonstrates the use and performance of our approach.

Network reliability studies properties of networks subjected to random failures of their components. It has been widely adopted to modeling and analyzing real-world problems across different domains, such as circuit design, genomics, databases, information propagation, network security, and many others. Two practical situations that usually arise from such problems are (i) the correlation between component failures and (ii) the uncertainty in failure probabilities. Previous work captured correlations by modeling component reliability using general Boolean expression of Bernoulli random variables. This paper extends such a model to address the second problem, where we investigate the use of Beta distributions to capture the variance of uncertainty. We call this new formalism the Beta uncertain graph. We study the reliability polynomials of Beta uncertain graphs as multivariate polynomials of Beta random variables and demonstrate the use of the model on two realistic examples. We also observe that the reliability distribution of a monotone Beta uncertain graph can be approximated by a Beta distribution, usually with high accuracy. Numerical results from Monte Carlo simulation of an approximation scheme and from two case studies strongly support this observation.

Most cyber attacks involve an attacker launching a multi-stage attack by exploiting a sequence of hosts. This multistage attack generates a chain of "stepping stones" from the origin to target. The choice of stepping stones is a function of the degree of exploitability, the impact, attacker's capability, masking origin location, and intent. In this paper, we model and analyze scenarios wherein an attacker employs multiple strategies to choose stepping stones. The problem is modeled as an Adjacency Quadratic Shortest Path using dynamic vulnerability graphs with multi-agent dynamic system approach. Using this approach, the shortest stepping stone attack with maximum node degree and the shortest stepping stone attack with maximum impact are modeled and analyzed.

A common function in networking is to find the best match between a packet's IP header and a list of matching rules, and to take some action based on the rule which is matched. This approach determines whether a packet transits a firewall or router and which interface is chosen for egress when it does, and whether a Network Address Translation transformation is applied. Considerable past research has optimized data structures and algorithms for rules-matching, under the operating assumption that with every specific application the best match is sought for a single IP flow, with a specified protocol, and specified source and destination IP and port numbers. This paper is motivated by a different scenario, in which we seek the simultaneous determination of the best matches for a bundle of flows. The flows are closely related as the bundle is a contiguous subset of the IP header space, meaning each flow draws in each dimension from the same range as other flows do in that same dimension. This specific problem arises in the design of tools that analyze the connectivity of networks. We consider here two algorithms for approaching this problem, which share the characteristic of generalizing the simulation of how devices typically classify a given flow. We study the behavior of these algorithms empirically, and find that the amortized cost of identifying the best matching rule in an ACL is typically measured in (at most) 10's of micro-seconds on an ordinary laptop computer.

Vulnerability graphs have been employed as an effective tool for analyzing exploitability and impact of chain of exploits in networked environments. The attack graphs are created by a chain of "stepping stones" from the attacker origin to the desired target. The stepping stones not only provide the intermediate steps to reach the target, but also make it difficulty to identify the attacker's true location. In this paper, we model and analyze stepping stones in dynamic vulnerability graphs. Most analysis based on attack graph assume that the graph edges and weights remain constant during the attacker's attempt to propagate through the network. We propose a biased min- consensus technique for dynamic graphs with switching topology as a distributed technique to determine the attach paths with more probable stepping-stones in dynamic vulnerability graphs. We use min-plus algebra to determine necessary and sufficient convergence conditions. A necessary condition for convergence to the shortest path in the switching topology case is provided.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

The applications in the critical infrastructure systems pose simultaneous resilience and performance requirements to the underlying computer network. To meet such requirements, the networks that use the store-and-forward paradigm poses stringent conditions on the redundancy in the network topology and results in problems that becoming computationally challenging to solve at scale. However, with the advent of programmable data-planes, it is now possible to use linear network coding (NC) at the intermediate network nodes to meet resilience requirements of the applications. To that end, we propose an architecture that realizes linear NC in programmable networks by decomposing the linear NC functions into the atomic coding primitives. We designed and implemented the primitives using the features offered by the P4 ecosystem. Using an empirical evaluation, we show that the theoretical gains promised by linear network coding can be realized with a per-packet processing cost.

Experience and intuition indicate that both synchronization and the mapping of workload to processors has significant impact on overall performance. However, the behavior of parallel simulations is quite complex, and the inter-relationships between workload mapping and the synchronization overheads need mathematical explanation. This paper develops a performance model of a parallel simulation that is synchronized using composite synchronization. We use this model to help explain how mapping decisions and a synchronization tuning parameter impacts synchronization overhead, and hence performance. The observations we make should inform designers of algorithms to map conservatively synchronized parallel simulations to the available computing platform.

Software defined networking (SDN) is an emerging technology for controlling flows through networks. Used in the context of industrial control systems, an objective is to design configurations that have built-in protection for hardware failures in the sense that the configuration has "baked-in" back-up routes. The objective is to leave the configuration static as long as possible, minimizing the need to have the controller push in new routing and filtering rules We have designed and implemented a tool that enables us to determine the complete connectivity map from an analysis of all switch configurations in the network. We can use this tool to explore the impact of a link failure, in particular to determine whether the failure induces loss of the ability to deliver a flow even after the built-in back-up routes are used. A measure of the original configuration's resilience to link failure is the mean number of link failures required to induce the first such loss of service. The computational cost of each link failure and subsequent analysis is large, so there is much to be gained by reducing the overall cost of obtaining a statistically valid estimate of resiliency. This paper shows that when analysis of a network state can identify all as-yet-unfailed links any one of whose failure would induce loss of a flow, then we can use the technique of importance sampling to estimate the mean number of links required to fail before some flow is lost, and analyze the potential for reducing the variance of the sample statistic. We provide both theoretical and empirical evidence for significant variance reduction.

Conjoinment of emulation and simulation in virtual time requires that emulated execution bursts be ascribed a duration in virtual time, and that emulated execution and simulation executions be coordinated within this common virtual time basis. This paper shows how an open source tool TimeKeeper for coordinating emulations in virtual time can be integrated with three different existing software emulations/simulations: CORE, ns-3, and S3F. We describe for each of these the modifications made to the tools to support this integration, and examine experiments designed to assess the accuracy of the combined models. Timekeeper permits much tighter sychronization emulation and simulation than has ever been achieved before.

The transformation of traditional power systems to smart grids brings significant benefits, but also exposes the grids to various cyber threats. The recent effort led by US National Electric Sector Cybersecurity Organization Resource (NESCOR) Technical Working Group 1 to compile failure scenarios is an important initiative to document typical cybersecurity threats to smart grids. While these scenarios are an invaluable thought-aid, companies still face challenges in systematically and efficiently applying the failure scenarios to assess security risks for their specific infrastructure. In this work, we develop a model-based process for assessing the security risks from NESCOR failure scenarios. We extend our cybersecurity assessment tool, Cyber-SAGE, to support this process, and use it to analyze 25 failure scenarios. Our results show that CyberSAGE can generate precise and structured security argument graphs to quantitatively reason about the risk of each failure scenario. Further, CyberSAGE can significantly reduce the assessment effort by allowing the reuse of models across different failure scenarios, systems, and attacker profiles to perform "what if?" analysis.

The University of Illinois at Urbana Champaign (Illinois), Pacific Northwest National Labs (PNNL), and the University of Southern California Information Sciences Institute (USC-ISI) consortium is working toward providing tools and expertise to enable collaborative research to improve security and resiliency of cyber physical systems. In this extended abstract we discuss the challenges and the solution space. We demonstrate the feasibility of some of the proposed components through a wide-area situational awareness experiment for the power grid across the three sites.

We present TimeKeeper: a simple lightweight approach to embedding Linux containers (LXC) in virtual time. Each container can be directed to progress in virtual time either more rapidly or more slowly than the physical wall clock time. As a result, interactions between an LXC and physical devices can be artificially scaled, e.g., to make a network appear to be ten times faster with respect to the software within the LXC than it actually is. Our approach also supports synchronized (in virtual time) emulation, by grouping LXCs together into an experiment where the virtual times of containers are kept synchronized, even when they advance at different speeds. This has direct application to the integration of emulation and simulation within a common framework.

Graph-based assessment formalisms have proven to be useful in the safety, dependability, and security communities to help stakeholders manage risk and maintain appropriate documentation throughout the system lifecycle. In this paper, we propose a set of methods to automatically construct security argument graphs, a graphical formalism that integrates various security-related information to argue about the security level of a system. Our approach is to generate the graph in a progressive manner by exploiting logical relationships among pieces of diverse input information. Using those emergent argument patterns as a starting point, we define a set of extension templates that can be applied iteratively to grow a security argument graph. Using a scenario from the electric power sector, we demonstrate the graph generation process and highlight its application for system security evaluation in our prototype software tool, Cyber SAGE.

In this paper we advocate the use of workflow---describing how a system provides its intended functionality---as a pillar of cybersecurity analysis and propose a holistic workflow-oriented assessment framework. While workflow models are currently used in the area of performance and reliability assessment, these approaches are designed neither to assess a system in the presence of an active attacker, nor to assess security aspects such as confidentiality. On the other hand, existing security assessment methods typically focus on modeling the active attacker (e.g., attack graphs), but many rely on restrictive models that are not readily applicable to complex (e.g., cyber-physical or cyber-human) systems.

Existing network architectures fall short when handling networking trends, e.g., mobility, server virtualization, and cloud computing, as well as market requirements with rapid changes. Software-defined networking (SDN) is designed to transform network architectures by decoupling the control plane from the data plane. Intelligence is shifted to the logically centralized controller with direct programmability, and the underlying infrastructures are abstracted from applications. The wide adoption of SDN in network industries has motivated development of large-scale, high-fidelity testbeds for evaluation of systems that incorporate SDN. We leverage our prior work on a hybrid network testbed with a parallel network simulator and a virtual-machine-based emulation system. In this paper, we extend the testbed to support OpenFlow-based SDN simulation and emulation; show how to exploit typical SDN controller behavior to deal with potential performance issues caused by the centralized controller in parallel discrete-event simulation; and investigate methods for improving the model scalability, including an asynchronous synchronization algorithm for passive controllers and a two-level architecture for active controllers. The techniques not only improve the simulation performance, but also are valuable for designing scalable SDN controllers.

There continues to be many advances in the theory and practice of Modeling and Simulation (M&S). However, some of these can be considered as Grand Challenges; issues whose solutions require significant focused effort across a community, sometimes with ground-breaking collaborations with new disciplines. In 2002, the first M&S Grand Challenges Workshop was held in Dagstuhl, Germany, in an attempt to focus efforts on key areas. In 2012, a new initiative was launched to continue these Grand Challenge efforts. Panel members of this third Grand Challenge present their views on M&S Grand Challenges. Themes presented in this panel include M&S Methodology; Agent-based M&S; M&S in Systems Engineering; Cyber Systems Modeling; and Network Simulation.

Integrated role-based access control (RBAC) and attribute-based access control (ABAC) is emerging as a promising paradigm. This paper proposes a framework that uses attribute-based policies to create a more traditional RBAC model. RBAC has been widely used, but has weaknesses: it is labor-intensive and time-consuming to build a model instance, and a pure RBAC system lacks flexibility to efficiently adapt to changing users, objects, and security policies. Particularly, it is impractical to manually make (and maintain) user to role assignments and role to permission assignments in industrial context characterized by a large number of users and/or security objects. ABAC has features complimentary to RBAC, and merging RBAC and ABAC has become an important research topic. This paper proposes a new approach to integrating ABAC with RBAC, by modeling RBAC in two levels. The aboveground level is a standard RBAC model extended with "environment". This level retains the simplicity of RBAC, supporting RBAC model verification/review. The "underground" level is used to represent security knowledge in terms of attribute-based policies, which automatically create the simple RBAC model in the aboveground level. These attribute-based policies bring to RBAC the advantages of ABAC: they are easy to build and easy to adapt to changes. Using this framework, we tackle the problem of permission assignment for large scale applications. This model is motivated by the characteristics and requirements of industrial control systems, and reflects in part certain approaches and practices common in the industry.

High assurance MILS and MLS systems require strict limitation of the interactions between different security compartments based on a security policy. Virtualization can be used to provide a high degree of separation in such systems. Even with perfect isolation, however, the I/O devices are shared between different security compartments. Among the I/O controllers, the graphics subsystem is the largest and the most complex. This paper describes the design and implementation of TrustGraph, a trusted graphics subsystem for high assurance systems. First, we explain the threats and attacks possible against an unsecured graphics subsystem. We then describe the design of TrustGraph, the security principles it is built upon, and its implementation. Finally, we verify our implementation through different levels of verification which include functionality testing for simple operations, attack testing for security mechanisms, and formal verification for the critical components of the implementation. An analysis of the graphics API covert channel attack is presented, its channel capacity is measured, and the capacity is reduced using the idea of fuzzy time.

This paper describes a project that integrates real devices used in the electric power grid with a simulation of electrical power generation and distribution, and a computer/communication simulator. The testbed is designed to evaluate the cyber-security of power grid control systems. Through a combination of simulation and emulation, the testbed seamlessly integrates virtual and real components, allowing for the evaluation of both high-level design descriptions on large-scale models, and precise measurements taken from production code executing on real hardware.

The Border Gateway Protocol (BGP) controls inter-domain routing in the Internet. BGP is vulnerable to many attacks, since routers rely on hearsay information from neighbors. Secure BGP (S-BGP) uses DSA to provide route authentication and mitigate many of these risks. However, many performance and deployment issues prevent S-BGP's real-world deployment. Previous work has explored improving S-BGP processing latencies, but space problems, such as increased message size and memory cost, remain the major obstacles. In this paper, we design aggregated path authentication schemes by combining two efficient cryptographic techniques---signature amortization and aggregate signatures. We propose six constructions for aggregated path authentication that substantially improve efficiency of S-BGP's path authentication on both speed and space criteria. Our performance evaluation shows that the new schemes achieve such an efficiency that they may overcome the space obstacles and provide a real-world practical solution for BGP security.

Summary form only given. As computational grids become an increasingly dominant force in the high-performance computing arena, the problem of efficiently transferring very large data sets, across geographically distributed computing resources, becomes increasingly difficult and important. Current approaches view the problem largely, if not exclusively, as a network-level problem. Thus all packet loss is interpreted and treated as a network congestion event, limiting the ability to detect or react to changes in the end-to-end system. We believe that a new approach to this problem is worth pursuing, and we are investigating techniques that can differentiate between data loss caused by contention in the network and loss caused by contention for shared CPU resources at the communication endpoints. The approach is to collect and analyze what we term packet-loss signatures that describe the patterns of packet-loss in the current transmission window. We analyze these signatures using Fourier analysis and symbolic dynamics, and present a simple set of experiments demonstrating the effectiveness of this approach.

The development of techniques for quantitative, model-based evaluation of computer system dependability has a long and rich history. A wide array of model-based evaluation techniques is now available, ranging from combinatorial methods, which are useful for quick, rough-cut analyses, to state-based methods, such as Markov reward models, and detailed, discrete-event simulation. The use of quantitative techniques for security evaluation is much less common, and has typically taken the form of formal analysis of small parts of an overall design, or experimental red team-based approaches. Alone, neither of these approaches is fully satisfactory, and we argue that there is much to be gained through the development of a sound model-based methodology for quantifying the security one can expect from a particular design. In this work, we survey existing model-based techniques for evaluating system dependability, and summarize how they are now being extended to evaluate system security. We find that many techniques from dependability evaluation can be applied in the security domain, but that significant challenges remain, largely due to fundamental differences between the accidental nature of the faults commonly assumed in dependability evaluation, and the intentional, human nature of cyber attacks.

This paper considers a technique for composing global (barrier-style) and local (channel scanning) synchronization protocols within a single parallel discrete-event simulation. Composition is attractive because it allows one to tailor the synchronization mechanism to the model being simulated. We first motivate the problem by showing the large performance gap that can be introduced by a mismatch of model and synchronization method. Our solution calls for each channel between submodels to be classified as synchronous or asynchronous. We mathematically formulate the problem of optimally classifying channels and show that, in principle, the optimal classification can be obtained in time proportional to max{C/spl times/log C, V/spl times/N}, where C is the number of channels, V the number of unique minimal delays on those channels, and N is the number of submodels. We then demonstrate an implementation which finds an optimal solution at runtime and consider its performance on network topologies, including one of the global Internet at the autonomous system level. We find that the automated method effectively determines channel assignments that maximize performance.

A comprehensive simulation model of wireless cellular networks must include the computation of transmitter power levels. In such systems, as time evolves, powers are continuously updated to minimize interference and maintain signal quality. Transmitters operate at the minimum power required to meet a target signal to noise ratio (SNR), which, in the real system, can be promptly estimated since the values involved come front direct measurements. In a simulation model, however, the interference over each receiver is a quantity that must be computed and the associated costs are not low. A system with N pairs of transmitters and receivers requires that O(N/sup 2/) pairwise interactions be computed; it's easy to see how very large the workload is when we consider that, in order to advance simulated time by one second, this large computation may have to be performed hundreds of times. We show that techniques devised for the simulation of systems of self-gravitating bodies (N-body problem) can be successfully applied to reduce the complexity of interference computations in simulations of wireless systems. However, our experiments suggest simple distance-based truncation may be the superior method.

The purpose of this paper is to describe a method for the simulation of the recently introduced fluid stochastic Petri nets. Since such nets result in rather complex system of partial differential equations, numerical solution becomes a formidable task. Because of a mixed (discrete and continuous) state space, simulative solution also poses some interesting challenges, which are addressed in the paper.

The paper describes the design and performance of IDES, a Java based distributed simulation engine being developed at Sandia National Laboratories. The feasibility of using Java is demonstrated by achieving order of magnitude speedup gains, on a model with three quarters of a million simulated entities, on an "off-the-shelf" system of 56 PentiumPro processors.

High-level formalisms such as stochastic Petri nets can be used to model complex systems. Analysis of logical and numerical properties of these models often requires the generation and storage of the entire underlying state space. This imposes practical limitations on the types of systems that can be modeled. Because of the vast amount of memory consumed, we investigate distributed algorithms for the generation of state space graphs. The distributed construction allows us to take advantage of the combined memory readily available on a network of workstations. The key technical problem is to find effective methods for on-the-fly partitioning, so that the state space is evenly distributed among processors. In this article we report on the implementation of a distributed state space generator that may be linked to a number of existing system modeling tools. We discuss partitioning strategies in the context of Petri net models, and report on performance observed on a network of workstations, as well as on a distributed memory multicomputer.

The Fast Fourier Transform (FFT) plays a key role in many areas of computational science and engineering. Although most one-dimensional FFT problems can be solved entirely in main memory, some important classes of applications require out-of-core techniques. For these, use of parallel I/O systems can improve performance considerably. This paper shows how to perform one-dimensional FFTs using a parallel disk system with independent disk accesses. We present both analytical and experimental results for performing out-of-core FFTs in two ways: using traditional virtual memory with demand paging, and using a provably asymptotically optimal algorithm for the Parallel Disk Model (PDM) of Vitter and Shriver. When run on a DEC 2100 server with a large memory and eight parallel disks, the optimal algorithm for the PDM runs up to 144.7 times faster than in-core methods under demand paging. Moreover, even including I/O costs, the normalized times for the optimal PDM algorithm are competitive, or better than, those for in-core methods even when they run entirely in memory.

We consider the problem of generating a large state-space in a distributed fashion. Unlike previously proposed solutions that partition the set of reachable states according to a hashing function provided by the user, we explore heuristic methods that completely automate the process. The first step is an initial random walk through the state space to initialize a search tree, duplicated in each processor. Then, the reachability graph is built in a distributed way, using the search tree to assign each newly found state to classes assigned to the available processors. Furthermore, we explore two remapping criteria that attempt to balance memory usage or future workload, respectively. We show how the cost of computing the global snapshot required for remapping will scale up for system sizes in the foreseeable future. An extensive set of results is presented to support our conclusions that remapping is extremely beneficial.

This paper considers the problem of bulk-loading large data sets for the gridfile multiattribute indexing technique. We propose a rectilinear partitioning algorithm that heuristically seeks to minimize the size of the gridfile needed to ensure no bucket overflows. Empirical studies on both synthetic data sets and on data sets drawn from computational fluid dynamics applications demonstrate that our algorithm is very efficient, and is able to handle large data sets. In addition, we present an algorithm for bulk-loading data sets too large to fit in main memory. Utilizing a sort of the entire data set it creates a gridfile without incurring any overflows.

We study a routing problem that arises on SIMD parallel architectures whose communication network forms a toroidal mesh. We assume there exists a set of k message descriptors {(xi, yi) ∣ i = 1, 2, …, k}, where (xi, yi) indicates that the ith message's recipient is offset from its sender by xi hops in one mesh dimension, and yi hops in the other. Every processor has k messages to send, and all processors use the same set of message descriptors. The SIMD constraint implies that at any routing step, every processor is actively routing messages with the same descriptors as any other processor. We call this Isomorphic Routing. Our objective is to find the isomorphic routing schedule with the minimum makespan. We consider a number of variations on the problem, yielding complexity results from O(k) to NP-complete. Most of our results follow after we transform the problem into a scheduling problem, where it is related to other well-known scheduling problems.

We consider the problem of statically assigning many tasks to a (smaller) system of homogeneous processors, where a task's structure is modeled as a branching process, all tasks are assumed to have identical behavior, and the tasks may synchronize frequently. We show how the theory of majorization can be used to obtain a partial order among possible task assignments. We show that if the vector of numbers of tasks assigned to each processor under one mapping is majorized by that of another mapping, then the former mapping is better than the latter with respect to a large number of objective functions. In particular, we show how the metrics of finishing time, the space-time product, and reliability are all captured. We also apply majorization to the problem of partitioning a pool of processors for distribution among parallelizable tasks. Limitations of the approach, which include the static nature of the assignment, are also discussed.

As massively parallel computers proliferate, there is growing interest in finding ways by which performance of massively parallel codes can be efficiently predicted. This problem arises in diverse contexts such as parallelizing compilers, parallel performance monitoring, and parallel algorithm development. In this paper, we describe one solution where one directly executes the application code, but uses a discrete-event simulator to model details of the presumed parallel machine, such as operating system and communication network behavior. Because this approach is computationally expensive, we are interested in its own parallelization, specifically the parallelization of the discrete-event simulator. We describe methods suitable for parallelized direct execution simulation of message-passing parallel programs, and report on the performance of such a system, LAPSE (Large Application Parallel Simulation Environment), we have built on the Intel Paragon. On all codes measured to date, LAPSE predicts performance well, typically within 10% relative error. Depending on the nature of the application code, we have observed low slowdowns (relative to natively executing code) and high relative speedups using up to 64 processors.

The complete-exchange communication primitive on a distributed memory multiprocessor calls for every processor to send a message to every other processor, each such message being unique. For circuit-switched hypercube networks there are two well-known schemes for implementing this primitive. Direct exchange minimizes communication volume but maximizes startup costs, while Standard Exchange minimizes startup costs at the price of higher communication volume. This paper analyzes a hybrid, which can be thought of as a sequence of Direct Echange phases, applied to variable-sized subcubes. This paper examines the problem of determining the optimal subcube dimension sizes di for every phase. We show that optimal performance is achieved using some equi-partition, where |di-dj|≤1 for all phases i and j. We study the behavior of the optimal partition as a function of machine communication parameters, hypercube dimension, and message size, and show that the optimal partition can be determined with no more than 2(d+1) comparisons. Finally we validate the model empirically, and for certain problem instances observe as much as a factor of two improvement over the other methods.

The availability of large-scale multitasked parallel architectures introduces the following processor assignment problem. We are given a long sequence of data sets, each of which is to undergo processing by a collection of tasks whose intertask data dependencies form a series-parallel partial order. Each individual task is potentially parallelizable, with a known experimentally determined execution signature. Recognizing that data sets can be pipelined through the task structure, the problem is to find a "good" assignment of processors to tasks. Two objectives interest us: minimal response time per data set, given a throughput requirement, and maximal throughput, given a response time requirement. Our approach is to decompose a series-parallel task system into its essential "serial" and "parallel" components; our problem admits the independent solution and recomposition of each such component. We provide algorithms for the series analysis, and use an algorithm due to Krishnamurti and Ma for the parallel analysis. For a p processor system and a series-parallel precedence graph with n constituent tasks, we give a O(np/sup 2/) algorithm that finds the optimal assignment (over a broad class of assignments) for the response time optimization problem; we find the assignment optimizing the constrained throughput in O(np/sup 2/ log p) time. These techniques are applied to a task system in computer vision.>

Considers the use of massively parallel architectures to execute a trace-driven simulation of a single cache set. A method is presented for the least-recently-used (LRU) policy, which, regardless of the set size C, runs in time O(log N) using N processors on the EREW (exclusive read, exclusive write) parallel model. A simpler LRU simulation algorithm is given that runs in O(C log N) time using N/log N processors. We present timings of this algorithm's implementation on the MasPar MP-1, a machine with 16384 processors. A broad class of reference-based line replacement policies are considered, which includes LRU as well as the least-frequently-used (LFU) and random replacement policies. A simulation method is presented for any such policy that, on any trace of length N directed to a C line set, runs in O(C log N) time with high probability using N processors on the EREW model. The algorithms are simple, have very little space overhead, and are well suited for SIMD implementation.>

The authors consider the static load balancing problem of assigning several large tasks to a (smaller) system of homogeneous processors, where a task's structure is modeled as a branching process, and all tasks are assumed to have stochastically identical behavior. They show how the theory of majorization can be used to obtain a partial order among possible task assignment. The power of this approach may be summarized as follows: a simple comparison between assignments creates an ordering between them that holds for a variety of objective functions as well as for several statistics such as the mean and variance. This partial ordering is particularly useful when heterogeneous constraints are placed on the numbers of tasks that one may assign to the processors. The results show that if the vector of numbers of tasks assigned to each processor under one mapping is majorized by that of another mapping, then the former mapping is better than the latter with respect to a large number of objective functions. In particular, it is shown how measurements of finishing time, resource utilization, and reliability are all captured by the theory.>

This paper describes a method for simulating a large class of queueing network models with Markovian phase-type distributions on parallel architectures. The method, which is based on uniformization, exploits Markovian properties that permit one to first build schedules of simulation times at which processors ought to synchronize, and then simulate a mathematically correct sample path through the pre-chosen schedule. While the technique eliminates many of the overheads incurred by other synchronization methods, it may suffer when the maximum rate (in simulation time) at which one processor might possibly ever send jobs to another is much larger than the average rate at which it actually does. We show how to reduce these overheads, sometimes doubling the execution rate as a result. We discuss experiments performed on the Intel iPSC/2 and Touchstone Delta architectures, where speedups in excess of 155 are observed on 256 processors.

This paper analytically studies the performance of a synchronous conservative parallel discrete-event simulation protocol. The class of models considered simulates activity in a physical domain, and possesses a limited ability to predict future behavior. Using a stochastic model, it is shown that as the volume of simulation activity in the model increases relative to a fixed architecture, the complexity of the average per-event overhead due to synchronization, event list manipulation, lookahead calculations, and processor idle time approaches the complexity of the average per-event overhead of a serial simulation, sometimes rapidly. The method is therefore within a constant factor of optimal. The result holds for the worst case “fully-connected” communication topology, where an event in any other portion of the domain can cause an event in any other protion of the domain. Our analysis demonstrates that on large problems—those for which parallel processing is ideally suited— there is often enough parallel workload so that processors are not usually idle. It also demonstrated the viability of the method empirically, showing how good performance is achieved on large problems using a thirty-two node Intel iPSC/2 distributed memory multiprocessor.

The authors describe parallel algorithms for simulating certain continuous time Markov chains, such as those arising in queueing network models of distributed computing systems or communications systems. The algorithms are based on the technique of uniformization. Two variations of a conservative parallel simulation algorithm are presented. In each algorithm, a relatively short presimulation is performed to identify those times, and only those times, at which the simulation algorithm requires processor pairs to synchronize. Speedup studies of the algorithms, performed on a 16-node Intel iPSC/2 hypercube, are presented and discussed.>

A conservative synchronization protocol for the parallel simulation of queuing networks having C job priority classes, where a job's class is fixed, is described. This problem has long vexed designers of conservative synchronization protocols because of its seemingly poor ability to compute lookahead: the time of the next departure. For, a job in service having low priority can be preempted at any time by an arrival having higher priority and an arbitrarily small service time. The solution is to slow the event generation activity so that events for higher priority jobs are generated farther ahead in simulated time than lower priority jobs. Thus. when a lower priority job enters service for the first time, all the higher priority jobs that may preempt it are already known and the job's departure time can be exactly predicted. The author analyzes the protocol and demonstrates that good performance can be expected on the simulation of large queuing networks.>

Formulas for estimating the probability of failure when testing reveals no errors are introduced. These formulas incorporate random testing results, information about the input distribution; and prior assumptions about the probability of failure of the software. The formulas are not restricted to equally likely input distributions, and the probability of failure estimate can be adjusted when assumptions about the input distribution change. The formulas are based on a discrete sample space statistical model of software and include Bayesian prior assumptions. Reusable software and software in life-critical applications are particularly appropriate candidates for this type of analysis.>

Recent work on the problem of mapping pipelined or parallel computations onto linear array, shared memory, and host-satellite systems is extended. It is shown how these problems can be solved even more efficiently when computation module execution times are bounded from below, intermodule communication times are bounded from above, and the processors satisfy certain homogeneity constraints. The improved algorithms have significantly lower time and space complexities than the more general algorithms: in one case, an O(nm/sup 3/) time algorithm for mapping m modules onto n processors is replaced with an O(nm log m) time algorithm, and the space requirements are reduced from O(nm/sup 2/) to O(m). Run-time complexity is reduced further with parallel mapping algorithms based on these improvements, which run on the architectures for which they create mappings.>

article Free Access Share on Analysis of synchronization in massively parallel discrete-event simulations Author: D. M. Nicol Department of Computer Science, College of William and Mary, Williamsburg, VA Department of Computer Science, College of William and Mary, Williamsburg, VAView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 25Issue 3Mar. 1990 pp 89–98https://doi.org/10.1145/99164.99174Online:01 February 1990Publication History 7citation318DownloadsMetricsTotal Citations7Total Downloads318Last 12 Months6Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Parallel computation offers the potential for quickly solving large computational problems. However, it is often a non-trivial task to effectively use parallel computers. Solution methods must sometimes be reformulated to exploit parallelism; the reformulations are often more complex than their slower serial counterparts. We illustrate these points by studying the parallelization of sparse one-dimensional dynamic programming problems, those which do not obviously admit substantial parallelization. We propose a new method for parallelizing such problems, develop analytic models which help us to identify problems which parallelize well, and compare the performance of our algorithm with existing algorithms on a multiprocessor. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A large class of data parallel computations is characterized by a sequence of phases, with phase changes occurring unpredictably. Dynamic remapping of the workload to processors may be required to maintain good performance. The problem considered, for which the utility of remapping and the future behavior of the workload are uncertain, arises when phases exhibit stable execution requirements during a given phase, but requirements change radically between phases. For these situations, a workload assignment generated for one phase may hinder performance during the next phase. This problem is treated formally for a probabilistic model of computation with at most two phases. The authors address the fundamental problem of balancing the expected remapping performance gain against the delay cost, and they derive the optimal remapping decision policy. The promise of the approach is shown by application to multiprocessor implementations of an adaptive gridding fluid dynamics program and to a battlefield simulation program.>

A formal analysis of a powerful mapping technique known as scatter decomposition is provided. Scatter decomposition divides an irregular computational domain into a large number of equally sized pieces and distributes them modularly among processors. A probabilistic model of workload in one dimension is used to formally explain why and when scatter decomposition works. The first result is that if a correlation in workload is a convex function of distance, then scattering a more finely decomposed domain yields a lower average processor workload variance. The second result shows that if the workload process is a stationary Gaussian and the correlation function decreases linearly in distance until becoming zero and then remain zero, scattering a more finely decomposed domain yields a lower expected maximum processor workload. It is shown that if the correlation function decreases linearly across the entire domain, then among all mappings that assign an equal number of domain pieces to each processor, scatter decomposition minimizes the average processor workload variance. The dependence of these results on the assumption of decreasing correlation is illustrated with situations where a coarser granularity actually achieves better load balance.>

Scientific codes are usually parallelized by partitioning a grid among processors. To achieve top performance it is necessary to partition the grid so as to balance workload and minimize communication/synchronization costs. This problem is particularly acute when the grid is irregular, changes over the course of the computation, and is not known until load-time. Critical mapping and remapping decisions rest on our ability to accurately predict performance, given a description of a grid and its partition. This paper discusses one approach to this problem, and illustrates its use on a one-dimensional fluids code. The models we construct are shown empirically to be accurate, and are used to find optimal remapping schedules.

B. Indurkhya et al. (1986) concluded that the optimal partitioning of a homogeneous random program over a homogeneous distributed system either assigns all modules to a single processor or distributes the modules as evenly as possible among all processors. Their analysis rests heavily on the approximation that equates the expected maximum of a set of independent random variables with the set's maximum expectation. The author strengthens this result by providing an approximation-free proof of this result for two processors under general conditions on the module execution time distribution. It is found that additional rigor leads to a different characterization of the optimality points. The author also shows that under a rigorous analysis one is led to different conclusions in the general P-processor case than those reached using B. Indurkhya et al.'s approximation.>

There exists substantial data level parallelism in scientific problems. The PARTY runtime system is an attempt to obtain efficient parallel implementations for scientific computations, particularly those where the data dependencies are manifest only at runtime. This can preclude compiler based detection of certain types of parallelism. The automated system is structured as follows: An appropriate level of granularity is first selected for the computations. A directed acyclic graph representation of the program is generated on which various aggregation techniques may be employed in order to generate efficient schedules. These schedules are then mapped onto the target machine. We describe some initial results from experiments conducted on the Intel Hypercube and the Encore Multimax that indicate the usefulness of our approach.

This paper derives upper bounds on the expected number of search tree nodes visited during an m-solution backtracking search, a search which terminates after some preselected number m problem solutions are found. The search behavior is assumed to have a general probabilistic structure. Our results are stated in terms of node expansion and contraction. A visited search tree node is said to be expanding if the mean number of its children visited by the search exceeds 1, and is contracting otherwise. We show that if every node expands, or if every node contracts, then the number of search tree nodes visited by a search has an upper bound which is linear in the depth of the tree, in the mean number of children a node has, and in the number of solutions sought. Bounds linear in the depth of the tree are derived for the case where the upper portion of the tree contracts while the lower portion expands. We derive linear bounds for some special cases of an expanding upper portion and contracting lower portion; however, in the general case we have exponentially complex bounds. While previous analyses of 1-solution backtracking have concluded that the expected performance is always linear in the tree depth, our model allows super-linear expected performance. By generalizing previous work in the expected behavior of backtracking, we are better able to identify classes of trees which can be searched in linear expected time.

The issue of deciding when to invoke a global load remapping mechanism is studied. Such a decision policy must effectively weigh the costs of remapping against the performance benefits, and should be general enough to apply automatically to a wide range of computations. The authors propose a general mapping decision heuristic, then study its effectiveness and its anticipated behavior on two very different models of load evolution. Assuming only that the remapping cost is known, this policy dynamically minimizes system degradation (including the cost of remapping) for each computation step. This policy is quite simple, choosing to remap when the first local minimum in the degradation function is detected. Simulations show that the decision obtained provides significantly better performance than that achieved by never remapping. The authors also observe that the average intermapping frequency is quite close to the optimal fixed remapping frequency.>