The increasing complexity and criticality of software systems have led to growing interest in automated test generation. One of the most promising approaches is to use model-based testing (MBT), in which test automation is based on a model of theimplementation under test (IUT), with much of the work concerning finite state machine (FSM) models. Many FSM-based test generation techniques use, possibly adaptive, sequences to check the state of the IUT. Of particular interest are adaptive distinguishing sequences (ADSs) because their use can lead to relatively small tests. However, not all systems possess an ADS. In this work, we generalise the notion of incomplete ADSs to non-deterministic partial and observable FSMs. We show that the problem of checking the existence of a set of$k$incomplete ADSs that separates every pair of states is PSPACE-hard. Further, we generalise the notion of invertible sequences to non-deterministic partial and observable FSMs and show how invertible sequences can be used to derive additional incomplete ADSs. We propose a novel algorithm to generate incomplete ADSs and describe the results of experiments that evaluated its performance. The results indicate that the proposed method can generate sequences to identify states of the IUT and is faster and can process larger FSMs than other existing methods.

In this paper we analytically solve the partitioning problem for performing matrix multiplication on a cluster of heterogeneous multicore machines, equipped with an accelerator, typically a GPU. We derive closed-form solutions that not only solve the problem in an exact manner, but they also allow for predictive analysis that can guide system design. Our work allows an optimum partitioning to be calculated in linear time with respect to the number of cores in the system. The static partitioning afforded by our Divisible Load Theory (DLT) based analysis, minimizes communication overhead and improves efficiency. Our work leverages existing optimized Dense Linear Algebra (DLA) libraries, such as cuBLAS and BLAS, which translates to an easy deployment that can readily exploit state-of-the-art tools. A comparison study concludes the paper, highlighting the beneficial effect of our partitioning approach.

GPUs are at the fore-front of a radical transformation that is taking place in software design. The ability to process multiple data streams simultaneously is delivering substantial benefits to a large collection of domains. Depending on the application, these benefits can be expanded by utilizing the not-insignificant power of traditional CPUs. Multi-core CPUs with a hierarchy of large and fast caches, can provide significant performance especially if data transfers dominate execution time, or branching does not allow for the uninterrupted execution on all GPU cores. In this paper we present an analytical framework that can be used to optimally consolidate CPU and GPU resources for the encryption/decryption of block ciphers such as AES. A rigorous set of experiments concludes the paper, showcasing the benefits and overall characteristics of the proposed framework. Our tests also bring to the surface important aspects of GPU operation that have to be taken into consideration upon the design of any successful scheduling scheme involving GPUs as a system component.

Image-content queries or image registration algorithms typically have very high computational requirements. In this paper, we address the problem of minimizing the total execution time of data-parallel image-content query algorithms on heterogeneous platforms. The model we use to capture the inner workings of these algorithms is comprehensive enough to incorporate not only the communication overheads, both distribution and result collection, but also the presence of local data caches that could exist as a result of previous queries. The problem is solved under all possible computation and communication configurations, including single and multiple-port communications and block or stream-type tasks. Our analysis, either, yields closed-form solutions to the partitioning problem, or, formulates the problem in a fashion that allows the use of linear programming tools toward this end. The latter are used for solving the multi-installment data distribution approaches, that tend to utilize the computational resources more efficiently. Additionally, a heuristic algorithm is presented, for producing a close-to-optimum sequence of load distribution/result collection operations for single-port communications. Based on our analytical results, a thorough simulation and experimental study is performed, yielding substantial design guidelines for implementation strategies.

One of the earliest applications that explored the power and flexibility of the grid computing paradigm was medical image matching. A typical characteristic of such applications is the large communication overheads due to the bulk of data that have to be transfered to the compute nodes. In this paper we study the problem of optimizing such applications under a broad model that incorporates not only communication overheads but also the existence of local data caches that could exist as a result of previous queries. Our analytical approach is not only complimented by a theorem that shows how to arrange the sequence of operations in order to minimize the overall cost, but also yields closed-form solutions to the partitioning problem. For the case where large load imbalances (due to big differences in cache sizes) prevent the calculation of a closed-form solution, we propose an algorithm for optimizing load redistribution. The paper is concluded by a simulation study that evaluates the impact of our analytical approach

Video transcoding is a popular technique for delivering video content of varying quality and size to diverse audiences. In this paper, we present a taxonomy of the different ways movie trans/en-coding can be performed by a multicomputer platform. We differentiate these techniques based on: (a) the party that performs the decoding of the input media stream; (b) whether the input data can be randomly accessed without the need for sequential decoding; and (c) the communication capabilities of the computing nodes. We then proceed to derive analytical closed-form solutions to the problem of optimizing the input data distribution to the nodes of the parallel machine in order to minimize the total execution time. This analysis is based on a systematic study of the costs associated with decoding and encoding movie frames by the FFMPEG OSS library. The paper is concluded by a simulation study based on a set of benchmarks performed on Linux workstations.

Video-on-demand (VoD) applications place very high requirements on the delivery medium. High-quality services should provide for a timely delivery of the data-stream to the clients plus a minimum of playback disturbances. The major contributions of this paper are that it proposes a multiserver, multi-installment (MSMI) solution approach (sending the document in several installments from each server) to the delivery problem and achieves a minimization of the client waiting time, also referred to as the access time (AT) or start-up latency in the literature. By using multiple spatially distributed servers, we are able to exploit slow connections that would otherwise prevent the deployment of video-on-demand-like services, to offer such services in an optimal manner. Additionally, the delivery and playback schedule that is computed by our approach is loss-aware in the sense that it is flexible enough to accommodate packet losses without interrupts. The mathematical framework presented covers both computation and optimization problems associated with the delivery schedule, offering a complete set of guidelines for designing MSMI VoD services. The optimizations presented include the ordering of the servers and determining the number of installments based on the packet-loss probabilities of the communication links. Our analysis guarantees the validity of a delivery schedule recommended by the system by providing a percentage of confidence for an uninterrupted playback at the client site. This, in a way, quantifies the degree of quality of service rendered by the system and the MSMI strategy proposed. The paper is concluded by a rigorous simulation study that showcases the substantial advantages of the proposed approach and explores how optimization of the schedule parameters affects performance.

The problem of optimally distributing a divisible load to the nodes of an arbitrary processor tree is tackled in this paper. The rigorous mathematical foundation presented allows the derivation of the sequence of operations that is necessary to obtain the minimum processing time, along with closed-form expressions that yield the solution in time O(NP), where P is the number of tree nodes and N their maximum degree. The main contributions of this work are: (1) both load distribution and result collection overheads are considered, thus providing better resource utilization, and (2) arbitrary processor trees are examined in contrast with previous approaches that examined either complete homogeneous trees, or single level trees. Additionally, approximate algorithms for solving the problem of specifying the optimum subset of active processors for a given load, are presented and evaluated.