Time and Energy Performance of Parallel Systems with Hierarchical Memory

In this paper we analyze the impact of memory hierarchies on time-energy trade-off in parallel computations. Contemporary computing systems have deep memory hierarchies with significantly different speeds and power consumptions. This results in nonlinear phenomena in the processing time and energy usage emerging when the size of the computation is growing. In this paper the nonlinear dependence of the time and energy on the size of the solved problem is formalized and verified using measurements in practical computer systems. Then it is applied to formulate a problem of minimum time and minimum energy scheduling parallel processing of divisible loads. Divisible load theory is a scheduling and performance model of data-parallel applications. Mathematical programming is exploited to solve the scheduling problem. A trade-off between energy and schedule length is analyzed and again nonlinear relationships between these two criteria are observed. Further performance analysis reveals that energy consumption and schedule length are ruled by a complex interplay between the costs and speeds of on-core and out-of-core computations, communication delays, and activating new machines.     

Constructive quantum scaling of unitary matrices

In this work, we present a method of decomposition of arbitrary unitary matrix \(U\in \mathbf {U}(2^k)\) into a product of single-qubit negator and controlled-\(\sqrt{\text{ NOT }}\) gates. Since the product results with negator matrix, which can be treated as complex analogue of bistochastic matrix, our method can be seen as complex analogue of Sinkhorn–Knopp algorithm, where diagonal matrices are replaced by adding and removing an one-qubit ancilla. The decomposition can be found constructively, and resulting circuit consists of \(O(4^k)\) entangling gates, which is proved to be optimal. An example of such transformation is presented.     

Central limit theorem for reducible and irreducible open quantum walks

In this work we aim at proving central limit theorems for open quantum walks on \({\mathbb {Z}}^d\). We study the case when there are various classes of vertices in the network. In particular, we investigate two ways of distributing the vertex classes in the network. First, we assign the classes in a regular pattern. Secondly, we assign each vertex a random class with a transition invariant distribution. For each way of distributing vertex classes, we obtain an appropriate central limit theorem, illustrated by numerical examples. These theorems may have application in the study of complex systems in quantum biology and dissipative quantum computation.     

Experiences with large-scale operational trials of ALTO-enhanced P2P filesharing in an intra-ISP scenario

Application Layer Traffic Optimization (ALTO) has recently gained attention in the research and standardisation community as a way for a network operator to guide the peer selection process of distributed applications by providing network layer topology information. In particular P2P applications are expected to gain from ALTO, due to the many connections peers form among each other, often without taking network layer topology information into account. In this paper, we present results of an extensive intra-ISP trial with an ALTO-enhanced P2P filesharing software. In summary, our results show that—depending on the concrete setting and on the distribution of upload capacity in the network—ALTO enables an ISP to save operational costs significantly while not degrading application layer performance noticeably. In addition, based on our experience we are able to give advice to operators on how to save costs with ALTO while not sacrificing application layer performance at all.     

Studies on a New Concept of 3D Data Integration about Reaches and Forces of a Disabled Person on a Wheelchair (CAD Methods in Car and Market Ergonomics)

The article presents a new concept of combining the three dimensions (3D) of a person's manipulation space. The data concern information about the reach of the arms and biomechanical data about limiting the load of a disabled person sitting in a wheelchair. Measurement data were acquired empirically, on original measuring station. The data included, respectively, arms' reach (static and dynamic) or, alternatively, measurements of limiting forces. The obtained data were processed into virtual 3D surfaces of arms' reach and forces. These surfaces provide the required graphic model of anthropotechnical and biomechanical data. Developed model was utilized to perform a virtual analysis of the accessibility of a disabled person to technical means: in a market sale space and in the ergonomic analysis into the space of a personal car. The presented method of 3D graphic modeling of anthropometrical and biomechanical data can be universally applied in ergonomic designing of work stations not only for disabled persons. © 2011 Wiley Periodicals, Inc.     

Code reordering using local random extraction and insertion (LREI) operator for GPGPU-based track-before-detect systems

Track-before-detect (TBD) algorithms are used for tracking systems, where the object’s signal is below the noise floor (low-SNR objects). A lot of computations and memory transfers for real-time signal processing are necessary. GPGPU in parallel processing devices for TBD algorithms is well suited. Finding optimal or suboptimal code, due to lack of documentation for low-level programming of GPGPUs is not possible. High-level code optimization is necessary and the evolutionary approach, based on the single parent and single child is considered, that is local search approach. Brute force search technique is not feasible, because there are N! code variants, where N is the number of motion vectors components. The proposed evolutionary operator—LREI (local random extraction and insertion) allows source code reordering for the reduction of computation time due to better organization of memory transfer and the texture cache content. The starting point, based on the sorting and the minimal execution time metric is proposed. The unbiased random and biased sorting techniques are compared using experimental approach. Tests shows significant improvements of the computation speed, about 8 % over the conventional code for CUDA code. The time period of optimization for the sample code is about 1 h (1,000 iterations) for the considered recursive spatio-temporal TBD algorithm.