Persistent Homology (PH) is a widely used tool of Topological Data Analysis (TDA) that measures the persistence of homological features present in data. PH is computed on a sequence of nested sub-complexes that form a filtration ${{\mathcal{K}}_{\mathcal{F}}}$ of data. In general, each nested sub-complex is defined by a scale parameter ϵ that defines the connectivity distances used to for its construction. These sub-complexes are arranged by increasing distances, ϵ0to ϵ∞, in the filtration; PH is then computed from ${{\mathcal{K}}_{\mathcal{F}}}$. However, due to its exponential space and time complexity, computing PH on big data is beyond the capabilities of contemporary machines. This paper explores the Piecewise computation of PH (PwPH) using subset constructions of the filtrations of data. PwPH is a framework for solutions that compute PH of data. In some embodiments, PwPH can be support computations of PH can be assembled into a complete picture of the homologies; in others, PwPH can only compute an approximation of the PH. The general solution of PwPH can be organized to use significantly less memory and provides a partition of computational PH elements that is, in some embodiments, embarrassingly parallel. This paper explores two complementary foundations to organize filtrations for PwPH.

Persistent Homology (PH) computes the persistence of homologies in data. Unfortunately, PH suffers from exponential complexity. Two important mechanisms used to attack this complexity are: (i) using Alpha complexes; and (ii) setting an upper bound on the dimensions of homology group dimensions reported. Unfortunately Alpha complexes cannot be constructed in a bounded subspace$\mathbb{R}^{s}$of the ambient dimension$\mathbb{R}^{n}(s < n)$, so they cannot be used together. This paper explores a mechanism that uses sparsified$\beta^{s}$-complexes to build Alpha complexes in bounded subspaces. The approach leverages Space-Partitioning$(SP)$trees to manage the generation of subspace$\beta^{s}$-meshes that are sufficient to preserve$H_{s}$homology features for data in$\mathbb{R}^{n}(s < n)$. This approach constructs sparsified$\beta^{s}$-complexes significantly faster and for larger data than previously possible. The sparsified$\beta^{s}$-complexes produce a family of complexes scalable to$\beta$; members of this family approximate a Vietoris-Rips complex when$\beta=0$and an Alpha complex in when$\beta=1$. Experimental results with$\beta^{s}$-complexes at$\beta=0$and$\beta=1$produce results from PH that mirror those using conventional constructions of Vietoris-Rips and Alpha complexes.

Topological Data Analysis (TDA) has demonstrated notable success in data mining by measuring the presence of topological structure in data. Persistent Homology (PH), one popular tool of TDA, examines the nested sequence of graphs formed over a data filtration to characterize unique homology classes. PH suffers from exponential complexity, limiting the approach to relatively small data sets and lower homology class applications. The Euler Characteristic Curve (ECC), a metric closely related to PH, can be computed more efficiently and, in some cases, can be used as a direct replacement to the applications of PH. A recent technique has been introduced to separate the ECC into dimensional components representing the homology classes identified by PH. This study examines the dimensional ECC, provides an improved algorithm, and introduces interpretation of the results as proximity-series representations of topological features; exploration of how to compare and classify ECC curves is detailed and shown in the context of MRA Brain Artery scan classification. Experimental results with ECC demonstrate the effectiveness and scalability to big data sets beyond that of current persistent homology applications.

Persistent Homology (PH) is a tool of Topological Data Analysis (TDA) that records the persistence of homologies in data. The persistence of the homologies is computed from a filtration of the data created at a set of increasing connectivity distances $\left(0=\epsilon_{0}, \epsilon_{1}, \cdots, \epsilon_{\max } \leq \infty\right)$. Unfortunately the time and space complexity of computing PH from simplicial complexes (Vietoris-Rips, Cech, or Alpha) or cubical complexes limits its scope of use to small and low dimensional data. This paper examines the use of a Polytopal Complex to represent the data using maximal polytopes as elements of the filtered complexes. Furthermore, the approach further reduces size of the polytopal complex with an externally supplied approximation factor $\delta$. The approximation preserves the homology of the space that extends beyond $\delta$. Experimental results shows a significant reduction in space requirements. The reduction in space complexity and the compromise in PH computation is proportional to $\delta$. In addition to efficient construction of polytopal complexes, this work computes the homology of space using a compact boundary matrix representation made possible by the polytopal complex. The polytopal complex also provides a significant reduction in topological representations of high dimensional data.

Abstract Persistent homology is a computationally intensive and yet extremely powerful tool for Topological Data Analysis. Applying the tool on potentially infinite sequence of data objects is a challenging task. For this reason, persistent homology and data stream mining have long been two important but disjoint areas of data science. The first computational model, that was recently introduced to bridge the gap between the two areas, is useful for detecting steady or gradual changes in data streams, such as certain genomic modifications during the evolution of species. However, that model is not suitable for applications that encounter abrupt changes of extremely short duration. This paper presents another model for computing persistent homology on streaming data that addresses the shortcoming of the previous work. The model is validated on the important real‐world application of network anomaly detection. It is shown that in addition to detecting the occurrence of anomalies or attacks in computer networks, the proposed model is able to visually identify several types of traffic. Moreover, the model can accurately detect abrupt changes of extremely short as well as longer duration in the network traffic. These capabilities are not achievable by the previous model or by traditional data mining techniques.

Persistent Homology is a computational method of data mining in the field of Topological Data Analysis. Large-scale data analysis with persistent homology is computationally expensive and memory intensive. The performance of persistent homology has been rigorously studied to optimize data encoding and intermediate data structures for high-performance computation. This paper provides an application-centric survey of the High-Performance Computation of Persistent Homology. Computational topology concepts are reviewed and detailed for a broad data science and engineering audience.

Persistent Homology (PH) is a method of Topological Data Analysis that analyzes the topological structure of data to help data scientists infer relationships in the data to assist in informed decision- making. A significant c omponent i n the computation of PH is the construction and use of a complex that represents the topological structure of the data. Some complex types are fast to construct but space inefficient w hereas others are costly to construct and space efficient. Unfortunately, existing complex types are not both fast to construct and compact.This paper works to increase the scope of PH to support the computation of low dimensional homologies (H0-H10) in high-dimension, big data. In particular, this paper exploits the desirable properties of the Vietoris-Rips Complex (VR-Complex) and the Delaunay Complex in order to construct a sparsified complex. The VR-Complex uses a distance matrix to quickly generate a complex up to the desired homology dimension. In contrast, the Delaunay Complex works at the dimensionality of the data to generate a sparsified c omplex. W hile construction of the VR-Complex is fast, its size grows exponentially by the size and dimension of the data set; in contrast, the Delaunay complex is significantly s maller f or a ny g iven d ata dimension. However, its construction requires the computation of a Delaunay Triangulation that has high computational complexity. As a result, it is difficult t o c onstruct a D elaunay C omplex for data in dimensions d > 6 that contains more than a few hundred points. The techniques in this paper enable the computation of topological preserving sparsification o f k -Simplices (where k ≪ d) to quickly generate a reduced sparsified complex sufficient t o c ompute h omologies u p t o k -subspace, irrespective of the data dimensionality d.

Topological Data Analysis (TDA) utilizes concepts from topology to analyze data. In general, TDA considers objects similar based on a topological invariant. Topological invariants are properties of the topological space that are homeomorphic; resilient to deformation in the space. The Euler-Poincaré Characteristic is a classic topological invariant that represents the alternating sum of the vertices, edges, faces, and higherorder cells of a closed surface. Tracking the Euler characteristic over a topological filtration produces an Euler Characteristic Curve (ECC). This study introduces a computational technique to determine the ECC of $\mathbb{R}^{2}$ or $\mathbb{R}^{3}$ data; the technique generalizes to higher dimensions. This technique separates landscapes of lowerorder homologies utilizing triangulations of the space.

Persistent Homology (PH) is computationally expensive and is thus generally employed with strict limits on the (i) maximum connectivity distance and (ii) dimensions of homology groups to compute (unless working with trivially small data sets). As a result, most studies with PH only work with H0and H1homology groups. This paper examines the identification and isolation of regions of data sets where high dimensional topological features are suspected to be located. These regions are analyzed with PH to characterize the high dimensional homology groups contained in that region. Since only the region around a suspected topological feature is analyzed, it is possible to identify high dimension homologies piecewise and then assemble the results into a scalable characterization of the original data set.

Topological Data Analysis is a machine learning method that summarizes the topological features of a space. Persistent Homology (PH) can identify these topological features as they persist within a point cloud; persisting in respect to the connectedness of the point cloud at increasing distances. The utility of PH is apparent in several fields including bioinformatics, network security, and object classification. However, the memory complexity of PH limits the application to relatively small point clouds for low-dimensional topological feature identification. For this reason, numerous approaches to optimize and approximate the PH have been introduced for providing results over large point clouds. One solution, Partitioned Persistent Homology (PPH), has shown favorable approximation on a single node with significant performance improvement. However, the single-node approach is limited by the available system memory, leading to the need for a distributed approach for additional (especially memory) resources. This paper studies a distributed version of PPH for use with large point clouds over a high-performance compute cluster. Experimental results of the distributed algorithm against previous studies is presented along with scalability of the distributed library.

An emerging method for data analysis is called Topological Data Analysis (TDA). TDA is based in the mathematical field of topology and examines the properties of spaces under continuous deformation. One of the key tools used for TDA is called persistent homology which considers the connectivity of points in a d-dimensional point cloud at different spatial resolutions to identify topological properties (holes, loops, and voids) in the space. Persistent homology then classifies the topological features by their persistence through the range of spatial connectivity. Unfortunately the memory and run-time complexity of computing persistent homology is exponential and current tools can only process a few thousand points in $\mathbb{R}^{3}$. Fortunately, the use of data reduction techniques enables persistent homology to be applied to much larger point clouds. Techniques to reduce the data range from random sampling of points to clustering the data and using the cluster centroids as the reduced data. While several data reduction approaches appear to preserve the large topological features present in the original point cloud, no systematic study comparing the efficacy of different data clustering techniques in preserving the persistent homology results has been performed. This paper explores the question of topology preserving data reductions and describes formally when and how topological features can be mischaracterized or lost by data reduction techniques. The paper also performs an experimental assessment of data reduction techniques and resilient effects on the persistent homology. In particular, data reduction by random selection is compared to cluster centroids extracted from different data clustering algorithms.

Persistent homology is a method of data analysis that is based in the mathematical field of topology. Unfortunately, the run-time and memory complexities associated with computing persistent homology inhibit general use for the analysis of big data. For example, the best tools currently available to compute persistent homology can process only a few thousand data points in ℝ3. Several studies have proposed using sampling or data reduction methods to attack this limit. While these approaches enable the computation of persistent homology on much larger data sets, the methods are approximate. Furthermore, while they largely preserve the results of large topological features, they generally miss reporting information about the small topological features that are present in the data set. While this abstraction is useful in many cases, there are data analysis needs where the smaller features are also significant (e.g., brain artery analysis). This paper explores a combination of data reduction and data partitioning to compute persistent homology on big data that enables the identification of both large and small topological features from the input data set. To reduce the approximation errors that typically accompany data reduction for persistent homology, the described method also includes a mechanism of “upscaling” the data circumscribing the large topological features that are computed from the sampled data. The designed experimental method provides significant results for improving the scale at which persistent homology can be performed.

Synthetic workloads are commonly used to exercise simulation tools for performance, performance tuning, and scalability studies. Sometimes these workloads are simple streams of test data following various distributions and in other cases these workloads are generated by more complex, configurable systems. An example of the former is a stream of input events at different arrival rates that might be used to test the performance of an event queue data structure. An example of the latter is the PHOLD simulation model that is often used to contrast the performance implications of different design solutions in a parallel simulation engine. One of the key challenges for synthetic workloads is the question of setting the parameters so that the workload properly reflects the behavior of actual workloads. This paper collects profile data from multiple real-world discrete-event simulation models in multiple configurations and sizes from the ROSS and WARPED2 repositories. A principle focus of this paper is the capture and reporting of profiling data to understand event granularities and event profile data to assist in the configuration of synthetic discrete event model generators.

Persistent homology is used for computing topological features of a space at different spatial resolutions. It is one of the main tools from computational topology that is applied to the problems of data analysis. Despite several attempts to reduce its complexity, persistent homology remains expensive in both time and space. These limits are such that the largest data sets to which the method can be applied have the number of points of the order of thousands in ℝ3. This paper explores a technique intended to reduce the number of data points while preserving the salient topological features of the data. The proposed technique enables the computation of persistent homology on a reduced version of the original input data without affecting significant components of the output. Since the run time of persistent homology is exponential in the number of data points, the proposed data reduction method facilitates the computation in a fraction of the time required for the original data. Moreover, the data reduction method can be combined with any existing technique that simplifies the computation of persistent homology. The data reduction is performed by creating small groups of similar data points, called nano-clusters, and then replacing the points within each nano-cluster with its cluster center. The persistence homology of the reduced data differs from that of the original data by an amount bounded by the radius of the nano-clusters. The theoretical analysis is backed by experimental results showing that persistent homology is preserved by the proposed data reduction technique.

The capture of data about the events executed by a discrete event simulation can easily lead to very large trace data files. While disk space is relatively inexpensive and mostly capable of storing these large trace files, the manipulation and analysis of these large trace files can prove difficult. Furthermore, some types of analysis must be performed in-core and they cannot be performed with the trace data exceeds the size of the physical RAM where the analysis is performed. Because of these limits, it is often necessary to strictly limit the simulation run time to satisfy the analysis time memory limits. Experience with the DESMetrics tool suite (a collection of tools to analyze event trace files), demonstrates that our in-memory analysis tools are limited to trace files on the order of 10GB (on a machine with 24GB of RAM). Furthermore, even when it is possible to analyze large trace files, the run time costs of performing this analysis can take several days to complete. While high performance analysis of traces data is not strictly necessary, the results should be available within some reasonably bounded time frame. This paper explores techniques to overcome the limits of analyzing very large event trace files. While explorations for out-out-core analysis have been examined as part of this work, the run time costs for out-of-core processing can increase processing time 10-fold. As a result, the work reported here will focus on an approach to capture and analyze small samples from the event trace file. The work reported in this paper will examine how closely the analysis from sampling matches the analysis from a full trace file. Two techniques for comparison are presented. First a visual comparison of analysis results between the full trace and a trace sample are presented. Second, numerical quantification of the different analysis results (between the full trace and trace sample) will be reported using the Wasserstein, Directed Hausdorff, and Kolmogorov-Smirnov distance metrics. Finally, the ability to process trace samples from a very large trace file of 80GB is demonstrated.

The set of events available for execution in a Parallel Discrete Event Simulation (PDES) are known as the pending event set. In a Time Warp synchronized simulation engine, these pending events are scheduled for execution in an aggressive manner that does not strictly enforce the causal relations between events. One of the key principles of Time Warp is that this relaxed causality will result in the processing of events in a manner that implicitly satisfies their causal order without paying the overhead costs of a strict enforcement of their causal order. On a shared memory platform the event scheduler generally attempts to schedule all available events in their Least TimeStamp First (LTSF) order to facilitate event processing in their causal order. By following an LTSF scheduling policy, a Time Warp scheduler can generally process events so that: (i) the critical path of the event timestamps is scheduled as early as possible, and (ii) causal violations occur infrequently. While this works effectively to minimize rollback (triggered by causal violations), as the number of parallel threads increases, the contention to the shared data structures holding the pending events can have significant negative impacts on overall event processing throughput. This work examines the application of profile data taken from Discrete-Event Simulation (DES) models to drive the simulation kernel optimization process. In particular, we take profile data about events in the schedule pool from three DES models to derive alternate scheduling possibilities in a Time Warp simulation kernel. Profile data from the studied DES models suggests that in many cases each Logical Process (LP) in a simulation will have multiple events that can be dequeued and executed as a set. In this work, we review the profile data and implement group event scheduling strategies based on this profile data. Experimental results show that event group scheduling can help alleviate contention and improve performance. However, the size of the event groups matters, small groupings can improve performance, larger groupings can trigger more frequent causal violations and actually slow the parallel simulation.

Performance and scalability of Parallel Discrete Event Simulation (PDES) is often limited by fine-grain communication, especially in execution environments with high communication cost. However, the low cost of on-chip communication in emerging many-core processors offers a promise to substantially alleviate conventional PDES bottlenecks. In this paper, we present a detailed evaluation and characterization of multi-threaded ROSS simulator on Intel's Knights Landing (KNL) processor. KNL is the second generation of the Intel Xeon Phi family of processors offering significant architecture improvements including 64 out-of-order multithreaded cores, sharing of some levels of the cache hierarchy among the cores, fast 2D mesh interconnect network and the ability to reconfigure the processor to support various clustering modes. We analyze the performance and scalability of ROSS simulator on KNL processor under different thread counts, communication patterns, event processing granularities, synchronization periods, thread placement policies, and workload partitioning schemes. We conclude that within a single KNL processor, up to 2X performance improvement can be achieved compared to commodity Xeon multicore processors. We show that in most cases the performance of ROSS scales well with the best results achieved when thread affinity is assigned, CPU cores are evenly loaded, cache sharing is exploited and communication is limited to small clusters of cores.

The expanding needs for analysis on large datasets has increased as the amount and availability of data continues to grow. The size and format of this data makes manual analysis infeasible and has motivated the drive for automated methods such as data clustering. Among the most commonly used clustering algorithms, K-means has been proven as one of the most popular choice that delivers acceptable results in reasonable time. For many years, K-means has proven to be statistically efficient and easy to implement. While K-means is widely used for clustering streaming data, it has performance issues when it comes to robustness with noise, parallelism and working with very large, high data sets. In particular, K-Means (and other conventional techniques) for data clustering do not parallelize or scale well with the increasing dimensionality of data.

The field of computer architecture uses quantitative methods to drive the computer system design process. By quantitatively profiling the run time characteristics of computer programs, the principal processing needs of commonly used programs became well understood and computer architects can focus their design solutions toward those needs. The DESMetrics project is established to follow this quantitative model by profiling the execution of Discrete Event Simulation (DES) models in order to focus optimization efforts within DES execution frameworks (and especially parallel DES engines). In particular, the DESMetrics project is designed to capture the run time characteristics of event execution in DES models. Because DES models tend to have fine grained computational processing requirements, the DESMetrics project focuses on the event dependencies and their exchange between the objects in the simulation. For now, we assume that optimization of the actual event processing is well served by conventional compiler and architecture solutions. Although, as will become clear later in Section 6, the possibility of identifying scheduling blocks of events that could potentially be schedule together can be achieved - at least within a single simulation object.

This paper presents a solution to the approximate k-means clustering problem for very large distributed datasets. Distributed data models have gained popularity in recent years following the efforts of commercial, academic and government organizations, to make data more widely accessible. Due to the sheer volume of available data, in-memory single-core computation quickly becomes infeasible, requiring distributed multiprocessing. Our solution achieves comparable clustering performance to other popular clustering algorithms, with improved overall complexity growth while being amenable to distributed processing frameworks such as Map-Reduce. Our solution also maintains certain guarantees regarding data privacy deanonimization.

Transactional memory is a concurrency control mechanism that dynamically determines when threads may safely execute critical sections of code. It provides the performance of fine-grained locking mechanisms with the simplicity of coarse-grained locking mechanisms. With hardware based transactions, the protection of shared data accesses and updates can be evaluated at runtime so that only true collisions to shared data force serialization. This paper explores the use of transactional memory as an alternative to conventional synchronization mechanisms for managing the pending event set in a Time Warp synchronized parallel simulator. In particular, we explore the application of Intel's hardware-based transactional memory (TSX) to manage shared access to the pending event set by the simulation threads. Comparison between conventional locking mechanisms and transactional memory access is performed to evaluate each within the warped Time Warp synchronized parallel simulation kernel. In this testing, evaluation of both forms of transactional memory found in the Intel Haswell processor, Hardware Lock Elision (HLE) and Restricted Transactional Memory (RTM), are evaluated. The results show that RTM generally outperforms conventional locking mechanisms and that HLE provides consistently better performance than conventional locking mechanisms, in some cases as much as 27%.

BACKGROUND: Forward Time Population Genetic Simulations offer a flexible framework for modeling the various evolutionary processes occurring in nature. Often this model expressibility is countered by an increased memory usage or computational overhead. With the complexity of simulation scenarios continuing to increase, addressing the scalability of the underlying simulation framework is a growing consideration. RESULTS: We propose a general method for representing in silico genetic sequences using implicit data structures. We provide a generalized implementation as a C++ template library called Clotho. We compare the performance and scalability of our approach with those taken in other simulation frameworks, namely: FWDPP and simuPOP. CONCLUSIONS: We show that this technique offers a 4x reduction in memory utilization. Additionally, with larger scale simulation scenarios we are able to offer a speedup of 6x-46x.

The rapid growth in the parallelism of multi-core processors has opened up new opportunities and challenges for parallel simulation discrete event simulation (PDES). PDES simulators attempt to find parallelism within the pending event set to achieve speedup. Typically the pending event set is sorted to preserve the causal orders of the contained events. Sorting is a key aspect that amplifies contention for exclusive access to the shared event scheduler and events are generally scheduled to follow the time-based order of the pending events. In this work we leverage a Ladder Queue data structure to partition the pending events into groups (called buckets) arranged by adjacent and short regions of time. We assume that the pending events within any one bucket are causally independent and schedule them for execution without sorting and without consideration of their total time-based order. We use the Time Warp mechanism to recover whenever actual dependencies arise. Due to the lack of need for sorting, we further extend our pending event data structure so that it can be organized for lock-free access. Experimental results show consistent speedup for all studied configurations and simulation models. The speedups range from 1.1 to 1.49 with higher speedups occurring with higher thread counts where contention for the shared event set becomes more problematic with a conventional mutex locking mechanism.

Multi-core and many-core processing chips are becoming widespread and are now being widely integrated into Beowulf clusters. This poses a challenging problem for distributed simulation as it now becomes necessary to extend the algorithms to operate on a platform that includes both shared memory and distributed memory hardware. Furthermore, as the number of on-chip cores grows, the challenges for developing solutions without significant contention for shared data structures grows. This is especially true for the pending event list data structures where multiple execution threads attempt to schedule the next event for execution. This problem is especially aggravated in parallel simulation, where event executions are generally fine-grained leading quickly to non-trivial contention for the pending event list.

BACKGROUND: In recent years genetic data analysis has seen a rapid increase in the scale of data to be analyzed. Schadt et al (NRG 11:647-657, 2010) offered that with data sets approaching the petabyte scale, data related challenges such as formatting, management, and transfer are increasingly important topics which need to be addressed. The use of succinct data structures is one method of reducing physical size of a data set without the use of expensive compression techniques. In this work, we consider the use of 2- and 3-bit encoding schemes for genotype data. We compare the computational performance of allele or genotype counting algorithms utilizing genotype data encoded in both schemes. RESULTS: We perform a comparison of 2- and 3-bit genotype encoding schemes for use in genotype counting algorithms. We find that there is a 20% overhead when building simple frequency tables from 2-bit encoded genotypes. However, building pairwise count tables for genome-wide epistasis is 1.0% more efficient. CONCLUSIONS: In this work, we were concerned with comparing the performance benefits and disadvantages of using more densely packed genotype data representations in Genome Wide Associations Studies (GWAS). We implemented a 2-bit encoding for genotype data, and compared it against a more commonly used 3-bit encoding scheme. We also developed a C++ library, libgwaspp, which offers these data structures, and implementations of several common GWAS algorithms. In general, the 2-bit encoding consumes less memory, and is slightly more efficient in some algorithms than the 3-bit encoding.

Current trends in desktop processor design have been toward many-core solutions with increased parallelism. As the number of supported threads grows in these processors, it may prove difficult to exploit them on the commodity desktop. This paper presents a study that explores the spawning of the dynamic memory management activities into a separately executing thread that runs concurrently with the main program thread. Our approach works without requiring modifications to the original source program by redefining the dynamic link path to capture malloc and free calls in a threading dynamic memory management library. The routines of this library are setup so that the initial call to malloc triggers the creation of a thread for dynamic memory management; successive calls to malloc and free will trigger coordination with this thread for dynamic memory management activities. Our preliminary studies show that we can transparently redefine the dynamic memory management activities and we have successfully done so for numerous test programs including most of the SPEC CPU2006 benchmarks, Firefox, and other unix utilities. The results of our experiments show that it is possible to achieve 2-3% performance gains in the three most memory-intensive SPEC CPU2006 benchmarks without requiring recompilation of the benchmark source code. We were also able to achieve a 3-4% speedup when using our library with the gcc and llvm compilers.

Packing (or executable compression) is considered as one of the most effective anti-reverse engineering methods in the Microsoft Windows environment. Even though many reversing attacks are widely conducted in the Linux-based embedded system there is no widely used secure binary code packing tools for Linux. This paper presents two secure packing methods that use AES encryption and the UPX packer to protect the intellectual property (IP) of software from reverse engineering attacks on Linux-based embedded system. We call these methods: secure UPX and AES-encryption packing. Since the original UPX system is designed not for software protection but for code compression, we present two anti-debugging methods in the unpacking module of the secure UPX to detect or abort reverse engineering attacks. Furthermore, since embedded systems are highly resource constrained, minimizing unpacking overhead is important. Therefore, we analyze the performance of the two packing methods from the perspective of: (i) code size, (ii) execution time, and (iii) power consumption. Our analysis results show that the Secure UPX performs better than AES-encryption packing in terms of the code size, execution time, and power consumption.

Abstract Time Warp distributed simulations can enter a catastrophic state of cascading rollbacks where out of order (premature) event executions propagate faster than the corrective measures (anti‐messages) designed to terminate them. In this paper, a distributed, proactive cancellation mechanism designed to avoid this situation is presented. We also present a version of total clocks calledPlausible Total Clocks(PTC). PTC employs a compact time vector ofevent counter rangeto address the scalability issues typically suffered by total clock solutions. That is, PTC consists of constant size vectors and are independent of the number of simulation objects in the simulation. The events generated due to an out of order execution are proactively cancelled by determining its causality relation with the already annihilated events. We present a proof of correctness of the distributed cancellation mechanism using PTC and also show that the catastrophic states are avoided with this proactive cancellation mechanism. This cancellation mechanism assumes first‐input–first‐output communication layer, static inter‐connection topology, and logical processes consisting of multiple simulation objects. Copyright © 2009 John Wiley & Sons, Ltd.

Optimistic time warp simulators should stop the rapid propagation of incorrect events to avoid reaching a catastrophic state (a state where out of order event execution is always a step ahead of its corrective measures). A distributed cancellation mechanism using total clocks was proposed earlier to avoid such catastrophic states. In this paper, we present a proactive cancellation mechanism using a vector of event counter range to address the scalability issues with the previously defined solution. As opposed to total clocks, this timestamp mechanism (a.k.a. plausible total clocks) consists of constant size vectors and are independent of the number of simulation objects in the simulation. The events generated due to an out of order execution are pro-actively canceled by determining its causality relation with the already annihilated events. We present a proof of correctness of the distributed cancellation mechanism and also show that catastrophic states are avoided with this proactive cancellation mechanism. This cancellation mechanism assumes FIFO communication layer, static inter-connection topology, and logical processes consisting of several simulation objects

The paper describes a formal framework developed using the Prototype Verification System (PVS) to model and verify distributed simulation kernels based on the Time Warp paradigm. The intent is to provide a common formal base from which domain specific simulators can be modeled, verified, and developed. PVS constructs are developed to represent basic Time Warp constructs. Correctness conditions for Time Warp simulation are identified, describing causal ordering of event processing and correct rollback processing. The PVS theorem prover and type-check condition system are then used to verify all correctness conditions. In addition, the paper discusses the framework's reusability and extensibility properties in support of specification and verification of Time Warp extensions and optimizations.

The integration of processing and DRAM offers a potential solution to the memory bottleneck problem. The bandwidth available within the chip is several orders of magnitude higher than that at the memory bus with a lower access time. As workloads shift towards data-intensive/multimedia applications, the wide bandwidth can be effectively utilized by harnessing the parallelism available in these applications. There are difficult challenges in developing architectures and programming models that expose the available bandwidth to the application. This paper presents the design of an intelligent memory based on a distributed data-parallel architecture with limited support for control parallelism. We investigate some of the relevant design issues and evaluate the success of such an architecture in supporting data-intensive applications. The design is evaluated as a stand-alone system, and also as a co-processor acting as a memory access filter. A cycle-accurate simulator is developed and used to study the performance of the architecture for data-intensive applications. The performance is compared against that of a modern superscalar processor.

The gap between the speed of logic and the DRAM memory access is widening. Traditional processors hide some of the mismatch in memory latency using techniques such as multi-level caches, instruction prefetching and memory interleaving. The bandwidth available at the system bus also forms a bottleneck; even an elaborate memory hierarchy with a perfect prefetching predictor generate memory traffic that overwhelms the capabilities of modern memory subsystems. A potential solution is the integration of DRAM and logic on the same die. Such solutions are motivated by the following: (i) the bandwidth available within the chip is many orders of magnitude higher than that at the memory bus at a significantly lower access time and with lower power dissipation; and (ii) as typical workloads shift towards data-intensive/multimedia applications, the wide bandwidth can be effectively utilized. However, there are significant challenges in developing architectures and programming models that expose the available bandwidth to end users. This paper presents the design of an intelligent memory based on a distributed data-parallel architecture with limited support for control parallelism (called PPIM). We investigate some of the relevant design issues and the success of such an architecture in supporting dataintensive applications. A cycle-accurate simulator is developed to study the architecture and performance for some data-intensive applications is compared against that of a modern superscalar processor (simulated using the simplescalar tool-set).

Web-based simulations are performed by utilizing the resources of the Word Wide Web (WWW) such as proprietary components/models developed by third party modelers /manufacturers and web-based computational infrastructures (or compute servers). Access to such web-based resources, third party resources in particular, is usually circumscribed by a variety of pricing schemes. Therefore, optimal use of resources plays a critical role in minimizing the overall costs of web-based modeling and simulation which is directly dependent on the size of the model i.e., the total number of components constituting the model. Consequently, component aggregation and de-aggregation techniques that can be used to statically (before simulation) as well as dynamically (during simulation) vary the number of components constituting a model, have been developed. The techniques enable a range of tradeoffs between several modeling and simulation related parameters -- thereby optimizing the resource consumption and overall costs. This paper presents a detailed discussion of the component aggregation and de-aggregation techniques along with the issues involved in implementing them in a Web-based Environment for Systems Engineering (WESE). Our studies indicate that these techniques provide an effective means to optimize the overall costs of web-based modeling and simulation.

Parallel simulation techniques are often employed to meet the computational requirements of large hardware simulations in order to reduce simulation time. In addition, partitioning for parallel simulations has been shown to be vital for achieving higher simulation throughput. This paper presents the results of our partitioning studies conducted on an optimistic-parallel logic simulation framework based on the time warp synchronization protocol. The paper also presents the design and implementation of a new partitioning algorithm based on a multilevel heuristic, developed as a part of this study. The multilevel algorithm attempts to balance load, maximize concurrency, and reduce inter-processor communication in three phases to improve performance. The experimental results obtained from our benchmarks indicate that the multilevel algorithm yields better partitions than other partitioning algorithms included in the study.

Discrete event simulations are widely used to study and analyze active and conventional networking architectures and protocols. Active networks must coexist and communicate with conventional networks to effectively utilize and extend the infrastructure of the Internet. Hence, large scale network simulations containing both conventional and active components should be conducted to study crucial scalability and performance issues. In this paper, a framework to enable parallel co-simulation of conventional and active networks is described. The framework integrates ANSE, a parallel active network simulation environment, with NS, a popular sequential network simulator. Object oriented techniques that completely insulate the application modules from the modifications have been employed for parallelizing NS in order to eliminate changes to the network models. This paper presents the design and implementation of the parallel co-simulation framework along with the results obtained from our co-simulation studies. Our studies indicate that parallel simulation techniques considerably reduce simulation times for even small sized network models.

The steady growth in size and complexity of communication networks has necessitated corresponding advances in the underlying networking technologies including communication protocols. This multi-faceted growth has rendered analysis of today's ultra-large networks, a complex task. Simulations have been used to model and analyze communication networks. Complete models of the ultra-large networks need to be simulated in order to study crucial scalability and performance issues. Discrete event simulations of such ultra-large networks, with limited hardware resources is complex due to their sheer size. This paper presents the issues involved in the design of a framework to enable ultra-large simulations, consisting of millions of nodes. The parallel simulation techniques used, the application program interface needed for model development, and the results from experiments conducted using the framework are also presented.

Formal models are used to provide an unambiguous definition of the semantics of very high speed integrated circuit hardware description language (VHDL) and to prove equivalences of VHDL programs. This paper presents a formal model of the dynamic semantics of VHDL that characterizes several important features of VHDL such as delta delays, pulse rejection limits, disconnection delays, postponed processes, sequential statements, and resolution functions. The underlying logic is interval temporal logic, which assists in characterizing the timing information contained in a VHDL program. The semantic definition is not dependent on the VHDL simulation cycle since it only defines the net effect of evaluating a VHDL program. It is argued that this declarative style coupled with the inherent advantages of temporal logic makes it possible to validate transformations (or rewrite rules) on VHDL programs and to formally reason about the timing aspects of VHDL. In particular, we present proofs of soundness of rewrite rules such as process folding and signal collapsing, and use temporal logic to derive an algorithm for determining when a given VHDL program is free of transaction preemption.

In time warp simulations, the overheads associated with rollbacks, state-saving and the communication induced by rollbacks are the chief contributors to the cost of the simulation; thus, these aspects of the simulation have been primary targets for optimizations. Unfortunately, the behavior of the time warp simulation is highly dynamic and greatly influenced by the application being simulated. Thus, the suggested optimizations are only effective for certain intervals of the simulation. This paper argues that the performance of time warp simulators benefits from a dynamic on-line decision process that selects and configures the sub-algorithms implementing the different aspects of the simulator to best match the current behavior of the simulation. In particular we study control strategies to dynamically: (i) adjust the checkpointing (or state-saving) interval (ii) select the cancellation strategy (lazy or aggressive), and (iii) determine the policy for aggregating the application messages (an optimization that significantly improves the performance in message passing environments). The strategies have been implemented in the WARPED time warp simulation kernel and the performance obtained via the dynamically controlled optimizations is shown to surpass that of their best performing static counterparts.

The paper describes extensions to VHDL to support system-level behavioral modeling by providing more abstract forms of communication and concurrency than those currently in the language. The report summarizes design objectives and issues that must be considered in developing such extensions, and presents definitions of our extensions. The extensions for communication consist of channel types, channel objects, dynamically allocated channels, and message passing statements. The extensions for concurrency consist of process declarations and static and dynamic process instantiation statements. Use of the extensions is illustrated with examples.

Mixed-Mode simulation has been generating considerable interest in the simulation community and has continued to grow as an active research area. Traditional mixed-mode simulation involves the merging of digital and analog simulators in various ways. However, efficient methods for the synchronization between the two time domains remains elusive. This is due to the fact that the analog simulator uses dynamic time step control whereas the digital simulator uses the event driven paradigm. This paper proposes two new synchronization methods and presents their capabilities using a component-based continuous time simulator integrated with an optimistic parallel discrete event simulator. The results of the performance evaluation leads us to believe that while both synchronization methods are functionally viable, one has superior performance.

Functional parallelism may be supported on SIMD machines by interpretation. The programs and data of each function are loaded on the processing elements (PEs), and the control unit of the machine executes a central control algorithm that causes the concurrent interpretation of these functions. The performance of this paradigm has been shown to benefit considerably from a variable instruction issue schedule that delays execution of expensive and rarely occurring operations. Two new features of the interpretation paradigm, namely pipelined SIMD machines and compositional instruction sets, change the nature of the mathematical model used for variable instruction scheduling significantly. In the paper, a previously developed mathematical model of the interpretation process is extended to allow for compositional instructions and pipelining. We develop and present algorithms that produce variable instruction schedules for the extended model and investigate whether the variable instruction issue is useful for these cases. We show that the variable instruction issue improves the performance of pipelined machines but is not very effective for compositional instruction sets, especially when the composition matrix is not sparse. © 1997 by John Wiley & Sons, Ltd.

Functional parallelism can be supported on SIMD machines by interpretation. Under such a scheme, the programs and data of each task are loaded on the processing elements (PEs) and the Control Unit of the machine executes a central control algorithm that causes the concurrent interpretation of the tasks on the PEs. The central control algorithm is, in many respects, analogous to the control store program on microprogrammed machines. Accordingly, the organization of the control algorithm greatly influences the performance of the synthesized MIMD environment. Most central control algorithms are constructed to interpret the execution phase of all instructions during every cycle (iteration). However, it is possible to delay the interpretation of infrequent and costly instructions to improve the overall performance. Interpreters that attempt improved performance by delaying the issue of infrequent instructions are referred to as variable issue control algorithms. This paper examines the construction of optimized variable issue control algorithms. In particular, a mathematical model for the interpretation process is built and two objective functions (instruction throughput and PE utilization) are defined. The problem of deriving variable issue control algorithms for these objective functions has been shown elsewhere to be NP-complete. Therefore, this paper investigates three heuristic algorithms for constructing near optimal variable issue control algorithms. The performance of the algorithms is studied on four different instruction sets and the trends of the schedulers with respect to the instruction sets and the objective functions are analyzed.

A hardware-software codesign environment provides the designer with an environment in which the designer can concurrently develop the hardware and software components of the system to satisfy a given set of performance and design constraints. As a design evolves from the conceptual level model of the hardware-software system, to the final implementation, the design progresses through a number of design steps and design environments. There exists a need for a single uniform design environment for specifying design information as it develops. In this paper, we describe our work to use VHDL to build design libraries that support rapid system prototyping and conceptual modeling as software components. Furthermore, the design libraries have been linked with a graphical codesign environment. This graphical environment provides a single framework in which the designer can (i) build the design, (ii) simulate the design for correctness, and (iii) visualize performance results and capacity measures.

The authors address one problem of speeding parallel digital system simulation using time warp, namely, that logical processes with errant behavior can incur considerable rollback behavior (analogous to thrashing in paging virtual memories). Consequently, additional mechanisms must be added to an optimistically synchronized simulator to inhibit excessive rollback. They describe a method of adaptively sizing bounded time windows to balance lookahead processing.>

A programming paradigm for massively parallel SIMD computers is described. The paradigm requires that each program be compiled into a special instruction set. Initially, the MINTABS software architecture's instruction set is used. A process is assigned to a processing element (PE) by storing its instructions and data at that PE. The control unit broadcasts a fixed control algorithm and the PEs use it to interpret their own program. Initial experiments have demonstrated an increase in throughput by a factor of more than 700 on an 8192-processor machine. The throughput also increases linearly with the number of processors.>

No abstract available.

A new and powerful model of computer architectures for machine description is presented. This model is capable of representing a machine across the abstraction levels ranging from the exo-architecture to the gate level. The goal is to establish a formal framework for the construction of a new hardware description language that will be useful for a large class of retargetable design-automation systems.>