3191261
Multiprocessor memory organization and memory interference
ture of shared memory in a multiprocessor computer system is examined with particular attention to noninterleaved memory. Alternative memory organizations are compared and it is shown that a home memory organization, in which each processor is associated with one or more memories in which its address space is concentrated, is quite effective in reducing memory interference. Home memory organization is shown to be particularly suited to certain specialized computational problems as well as to possess advantages in terms of interference and reliability for general purpose computation. Results for interleaved memory are drawn from previous work and are used for comparison. Trace-driven simulations are used to verify the conclusions of the analysis.
32709902
Disk Cache Design and Performance as Evaluated in Large Timesharing and Database Systems
14158820
Disk caching in large database and timeshared systems
We present the results of a variety of trace-driven simulations of disk cache designs using traces from a variety of mainframe timesharing and database systems in production use. We compute miss ratios, run lengths, traffic ratios, cache residency times, degree of memory pollution and other statistics for a variety of designs, varying lock size, prefetching algorithm and write algorithm. We find that for this workload, sequential prefetching produces a significant (about 20%) but still limited improvement in the miss ratio, even using a powerful technique for detecting sequentiality. Copy-back writing decreased write traffic relative to write-through by more than 50%; periodic flushing of the dirty blocks increased write traffic only slightly compared to pure write-back, and then only for large cache sizes. Write-allocate had little effect compared to no-write-allocate. Block sizes of over a track don't appear to be useful. Limiting cache occupancy by a single process or transaction appears to have little effect. This study is unique in the variety and quality of the data used in the studies.
14423694
Characteristics of I/O traffic in personal computer and server workloads
Understanding the characteristics of I/O traffic is increasingly important as the performance gap between the processor and disk-based storage continues to widen. Moreover, recent advances in technology, coupled with market demands, have led to new and exciting developments in storage systems, particularly network storage, storage utilities, and intelligent self-optimizing storage. In this paper, we empirically examine the physical I/O traffic of a wide range of server and personal computer (PC) workloads, focusing on how these workloads will be affected by the recent developments in storage systems. As part of our analysis, we compare our results with historical data and re-examine some rules of thumb (e.g., one bit of I/O per second for each instruction per second of processing power) that have been widely used for designing computer systems. We find that the I/O traffic is bursty and appears to exhibit self-similar characteristics. Our analysis also indicates that there is little cross-correlation between traffic volumes of server workloads, which suggests that aggregating these workloads will likely help to smooth out the traffic and enable more efficient utilization of resources. We discover that there is significant potential for harnessing "free" system resources to perform background tasks such as optimization of disk block layout. In general, we observe that the characteristics of the I/O traffic are relatively insensitive to the extent of upstream caching, and thus our results still apply, on a qualitative level, when the upstream cache is increased in size.
36108373
Machine Characterization Based on an Abstract High-Level Language Machine
Measurements are presented for a large number of machines ranging from small workstations to supercomputers. The authors combine these measurements into groups of parameters which relate to specific aspects of the machine implementation, and use these groups to provide overall machine characterizations. The authors also define the concept of pershapes, which represent the level of performance of a machine for different types of computation. A metric based on pershapes is introduced that provides a quantitative way of measuring how similar two machines are in terms of their performance distributions. The metric is related to the extent to which pairs of machines have varying relative performance levels depending on which benchmark is used. >
2307317
Improving dynamic voltage scaling algorithms with PACE
This paper addresses algorithms for dynamically varying (scaling) CPU speed and voltage in order to save energy. Such scaling is useful and effective when it is immaterial when a task completes, as long as it meets some deadline. We show how to modify any scaling algorithm to keep performance the same but minimize expected energy consumption. We refer to our approach as PACE (Processor Acceleration to Conserve Energy) since the resulting schedule increases speed as the task progresses. Since PACE depends on the probability distribution of the task's work requirement, we present methods for estimating this distribution and evaluate these methods on a variety of real workloads. We also show how to approximate the optimal schedule with one that changes speed a limited number of times. Using PACE causes very little additional overhead, and yields substantial reductions in CPU energy consumption. Simulations using real workloads show it reduces the CPU energy consumption of previously published algorithms by up to 49.5%, with an average of 20.6%, without any effect on performance.
7048039
Establishing Communication Systems without Explicit Meaning Transmission
This paper investigates the development of experience-based meaning creation and explores the problem of establishing successful communication systems in a population of agents. The aim of the work is to investigate how such systems can develop, without reliance on phenomena not found in actual human language learning, such as the explicit transmission of meaning or the provision of reliable error feedback to guide learning. Agents develop individual, distinct meaning structures, and although they can communicate despite this, communicative success is closely related to the proportion of shared lexicalised meaning, and the communicative systems have a large degree of redundant synonymy.
5725147
Local search genetic algorithm for optimal design of reliable networks
This paper presents a genetic algorithm (GA) with specialized encoding, initialization, and local search operators to optimize the design of communication network topologies. This NP-hard problem is often highly constrained so that random initialization and standard genetic operators usually generate infeasible networks. Another complication is that the fitness function involves calculating the all-terminal reliability of the network, which is a computationally expensive calculation. Therefore, it is imperative that the search balances the need to thoroughly explore the boundary between feasible and infeasible networks, along with calculating fitness on only the most promising candidate networks. The algorithm results are compared to optimum results found by branch and bound and also to GA results without local search operators on a suite of 79 test problems. This strategy of employing bounds, simple heuristic checks, and problem-specific repair and local search operators can be used on other highly constrained combinatorial applications where numerous fitness calculations are prohibitive.
37361807
Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets
Consider two parties holding correlated random variables W and W′, respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys {Rj} using multiple pairs {(Wj, W′j)}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors. 
 
Our results improve upon previous work in several respects: 
 
– The best previous solution for the keyless case with no errors (i.e., t=0) requires the min-entropy of W to exceed 2|W|/3. We show a solution when the min-entropy of W exceeds the minimal threshold |W|/2. 
 
– Previous solutions for the keyless case in the presence of errors (i.e., t>0) required random oracles. We give the first constructions (for certain metrics) in the standard model. 
 
– Previous solutions for the keyed case were stateful. We give the first stateless solution.
1925819
Authentication of quantum messages
Authentication is a well-studied area of classical cryptography: a sender A and a receiver B sharing a classical secret key want to exchange a classical message with the guarantee that the message has not been modified or replaced by a dishonest party with control of the communication line. In this paper we study the authentication of messages composed of quantum states. We give a formal definition of authentication in the quantum setting. Assuming A and B have access to an insecure quantum channel and share a secret, classical random key, we provide a non-interactive scheme that enables A to both encrypt and authenticate an m qubit message by encoding it into m+s qubits, where the error probability decreases exponentially in the security parameter s. The scheme requires a secret key of size 2m+O(s). To achieve this, we give a highly efficient protocol for testing the purity of shared EPR pairs. It has long been known that learning information about a general quantum state will necessarily disturb it. We refine this result to show that such a disturbance can be done with few side effects, allowing it to circumvent cryptographic protections. Consequently, any scheme to authenticate quantum messages must also encrypt them. In contrast, no such constraint exists classically. This reasoning has two important consequences: It allows us to give a lower bound of 2m key bits for authenticating m qubits, which makes our protocol asymptotically optimal. Moreover, we use it to show that digitally signing quantum states is impossible.
15197279
On the complexity of finding common approximate substrings
Problems associated with finding strings that are within a specified Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBSTRING (CAS) problem. Our analyses indicate under which parameter restrictions useful algorithms are possible, and include both class membership and parameterized reductions to prove class hardness. In order to achieve fixed-parameter tractability, either a fixed string length or both a fixed size alphabet and fixed substring length are sufficient. Fixing either the string length or the alphabet size and Hamming distance is shown to be necessary, unless W[1] = FPT. An assortment of parameterized class membership and hardness results cover all other parameterized variants, showing in particular the effect of fixing the number of strings.