ABSTRACT We investigate the performance of algorithms that explore large state graphs of finite state machines without input by following paths. To improve on anchor‐based and candidate‐based explorations and to avoid the performance overhead of full anchor lists and the tuning sensitivity of timeout‐based methods, we propose and analyze exploration based on two combinations: two sets of candidate nodes and candidate nodes plus a restricted form of anchors. We confirm our analysis by experiments on a multicore machine: both combinations achieve similar performance, with slight differences depending on the input graph and with respect to accuracy of secondary information like the point of entry into the cycle. The method with two candidate sets provides accurate information also on the tail length, while the method with candidates and restricted anchors often yields best performance.

We investigate decimal number representations in large data streams. When decimal numbers are encoded in bits, not all possibilities are used. This opens possibilities to establish a covert channel, i.e., to inject secret data into the data stream and transport it hidden in the mass of data, which poses a security risk, as covert channels are mostly used for criminal purposes. We present a novel covert channel approach for streams of decimal data, a field which so far has been neglected. Moreover, we sketch an application scenario and analyze the covert channel's detectability, in particular how detectability and steganographic bandwidth can be traded against each other. The approach and proposals for detection are tested via simulation experiments.

Higher-radix floating-point representations have the potential for higher performance, lower energy footprint, and reduced gate count in embedded systems when compared to traditional binary floating-point numbers. Thus, they might also appear in transmission of sensor data values. However, these number formats introduce redundancies, which can be exploited for steganographic message transfer. We present a covert channel that exploits this redundancy and can trade steganographic bandwidth against introduced error and thus detectability. In the basic variant, the covert channel is fully reversible, i.e., not detectable from the data. Experiments with an implementation illustrate that detectability via compressibility metric, Shannon entropy and bi-grams is possible depending on how aggressive bandwidth is pushed.

Summary Streaming task graphs are high‐level specifications for parallel applications operating on streams of data. For a static task graph structure, static schedulers can be used to map the tasks onto a parallel platform to minimize energy consumption for given throughput. We introduce dynamic elements into the task graph structure, thus specifying applications which adapt behavior at runtime, for example, switching from check‐only to active mode. This in turn necessitates a runtime system that can remap tasks and potentially adapt their degree of parallelism in case of a dynamic change of the task structure. We provide a toolchain and evaluate our prototype with streaming task graphs both synthetic and from a real application. We find that we meet throughput requirements with <3.5% energy overhead on average compared with an optimal static scheduler based on integer linear programming. Runtime overhead for remapping is negligible and application runtime and energy are accurately predicted. We also outline how to extend our system to a heterogeneous platform.

Abstract Terrorism is a scourge of humanity. Thousands of people were killed by terrorists in the last years. To understand the structure, information flow and leadership in terrorist cells is a must for all societies to prevent future attacks. Network theory can help to model such cells and to identify leading members therein. This contribution uses the graph theoretical approach as a basis and enriches it by an entropy‐driven knowledge processing. After presenting the theoretical concept two terrorist cells, the one of the Bali attack and the one of the 9/11 attack, are analysed. The results are compared to those of other methods. A preview on the application of weighted networks and multi‐nets complements the new findings.

Static scheduling of independent, moldable tasks on parallel machines with frequency scaling comprises decisions on core allocation, assignment, frequency scaling and ordering, to meet a deadline and minimize energy consumption. Constraining some of these decisions reduces the solution space, i.e. may increase energy consumption, but may also open the path to new, near-optimal approaches. We investigate how constraints of different steps influence energy consumption, starting with an unrestricted scheduler for moldable tasks. The constraints are partly derived from existing schedulers, but also generalized in a systematic way. We present integer linear programs for all scheduling variants. We compare energy consumption of schedules for a benchmark suite of synthetic task sets of different sizes and for task sets derived from real applications. In addition, we check how close the results are to the optimum results when the ILP solver meets a timeout. Our results indicate that constraints on task execution order, which avoid explicit representation of task order in ILPs, are mostly responsible for near-optimal energy consumption among large task sets. Furthermore, we find that for all steps except allocation, non-optimal fast heuristics can be used without sacrificing too much energy for the resulting schedule. Finally, we can show that an ILP for a new scheduler, for which also a heuristic version exists, is comparable in quality to more complicated schedulers.

Crown scheduling is a static scheduling approach for sets of parallelizable tasks with a common deadline, aiming to minimize energy consumption on parallel processors with frequency scaling. We demonstrate that crown schedules are robust, i. e. that the runtime prolongation of one task by a moderate percentage does not cause a deadline transgression by the same fraction. In addition, by speeding up some tasks scheduled after the prolonged task, the deadline can still be met at a moderate additional energy consumption. We present a heuristic to perform this re-scaling online and explore the tradeoff between additional energy consumption in normal execution and limitation of deadline transgression in delay cases. We evaluate our approach with scheduling experiments on synthetic and application task sets. Finally, we consider influence of heterogeneous platforms such as ARM’s big.LITTLE on robustness.

Croivn scheduling is a static scheduling approach for sets of parallelizable tasks with a common deadline, aiming to minimize energy consumption on parallel processors with frequency scaling. We demonstrate that crown schedules are robust, i.e. that the runtime prolongation of one task by a moderate percentage does not cause a deadline transgression by the same fraction. In addition, by speeding up some tasks scheduled after the prolonged task, the deadline can still be met at a moderate additional energy consumption. We present a heuristic to perform this re-scaling online. We evaluate our approach with scheduling experiments on synthetic task sets.

We consider static scheduling of parallelizable tasks onto machines with frequency scaling for the case that not all tasks can be executed prior to a deadline. We model this scenario from a HPC cluster operator's perspective. We solve the combinatorial optimization problem to maximize the operator's profit by integer linear programming and by a heuristic. We evaluate the heuristic with synthetic benchmark task sets and demonstrate that it achieves at most 20 % less profit than the solution via linear programming, so that it can be used for large task sets where the latter is not feasible anymore.

We consider the problem of statically scheduling a task graph of moldable streaming tasks (i.e., the actor network) to a multicore or many-core CPU with discrete dynamic voltage and frequency scaling (DVFS). We employ an integer linear programming (ILP) approach that combines allocating cores to tasks, mapping tasks to core subsets, selecting a DVFS level for each task, and considering all options for task fusion as provided by a cost model, given data throughput and latency requirements and targeting low energy consumption. We also propose a partly decoupled approach that applies greedy prefusion before running an ILP-based scheduler considering the other three subproblems together. We use microbenchmarking on an ARM big.LITTLE architecture to quantify the advantage of task fusion in the above setting, and evaluate the use of task fusion in terms of energy savings, latency improvement, and scheduling time for three real-world applications. We confirm the scheduling results by running the applications with and without task fusions on the ARM big.LITTLE. Results indicate that streaming applications can profit from task fusion, as we achieve a significant reduction of energy consumption in most cases, while scheduling time is only moderately increased.