9697967
Disk cache—miss ratio analysis and design considerations
The current trend of computer system technology is toward CPUs with rapidly increasing processing power and toward disk drives of rapidly increasing density, but with disk performance increasing very slowly if at all. The implication of these trends is that at some point the processing power of computer systems will be limited by the throughput of the input/output (I/O) system.
A solution to this problem, which is described and evaluated in this paper, is disk cache. The idea is to buffer recently used portions of the disk address space in electronic storage. Empirically, it is shown that a large (e.g., 80-90 percent) fraction of all I/O requests are captured by a cache of an 8-Mbyte order-of-magnitude size for our workload sample. This paper considers a number of design parameters for such a cache (called cache disk or disk cache), including those that can be examined experimentally (cache location, cache size, migration algorithms, block sizes, etc.) and others (access time, bandwidth, multipathing, technology, consistency, error recovery, etc.) for which we have no relevant data or experiments. Consideration is given to both caches located in the I/O system, as with the storage controller, and those located in the CPU main memory. Experimental results are based on extensive trace-driven simulations using traces taken from three large IBM or IBM-compatible mainframe data processing installations. We find that disk cache is a powerful means of extending the performance limits of high-end computer systems.
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.
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.
11584462
The automatic improvement of locality in storage systems
Disk I/O is increasingly the performance bottleneck in computer systems despite rapidly increasing disk data transfer rates. In this article, we propose Automatic Locality-Improving Storage (ALIS), an introspective storage system that automatically reorganizes selected disk blocks based on the dynamic reference stream to increase effective storage performance. ALIS is based on the observations that sequential data fetch is far more efficient than random access, that improving seek distances produces only marginal performance improvements, and that the increasingly powerful processors and large memories in storage systems have ample capacity to reorganize the data layout and redirect the accesses so as to take advantage of rapid sequential data transfer. Using trace-driven simulation with a large set of real workloads, we demonstrate that ALIS considerably outperforms prior techniques, improving the average read performance by up to 50% for server workloads and by about 15% for personal computer workloads. We also show that the performance improvement persists as disk technology evolves. Since disk performance in practice is increasing by only about 8% per year, the benefit of ALIS may correspond to as much as several years of technological progress.
36713689
Performance Characterization of Optimizing Compilers
Optimizing compilers have become an essential component in achieving high levels of performance. Various simple and sophisticated optimizations are implemented at different stages of compilation to yield significant improvements, but little work has been done in characterizing the effectiveness of optimizers, or in understanding where most of this improvement comes from. We study the performance impact of optimization in the context of our methodology for CPU performance characterization based on the abstract machine model. The model considers all machines to be different implementations of the same high level language abstract machine; in previous research, the model has been used as a basis to analyze machine and benchmark performance. We show that our model can be extended to characterize the performance improvement provided by optimizers and to predict the run time of optimized programs, and measure the effectiveness of several compilers in implementing different optimization techniques. >
12460438
Evaluation of cache consistency algorithm performance
As more computer systems turn to multiprocessing for improved performance, additional research is needed to evaluate and improve the performance of cache consistency protocols. In this study, we use trace-driven simulation to examine the performance of several consistency protocols, including some new adaptive protocols which have not been examined in prior research. This study uses a wider variety of traces than have been previously analyzed, including some production applications from a vector mini-supercomputer system, and presents a wider variety of analyses than have been previously presented for a given workload. We find that the sharing characteristics of application programs have a large bearing on the relative performance of the different protocols. Update-based protocols outperform invalidate-based protocols when accesses so shared data are highly interleaved among different processors (fine-grain sharing), while invalidate-based protocols are superior if one processor performs all accesses to shared data over long periods of time (coarse-grain sharing). Adaptive protocols provide the best overall performance across all applications; we present a new protocol called Update-Once, which yields the highest average performance. In even the best cases, however, estimated processor utilizations are unacceptably low due to the overhead to maintain consistent caches. To extract good performance from multiprocessor systems, existing application programs must be recoded to reduce sharing between processors.
10194960
Secure Remote Authentication Using Biometric Data
Biometric data offer a potential source of high-entropy, secret information that can be used in cryptographic protocols provided two issues are addressed: (1) biometric data are not uniformly distributed; and (2) they are not exactly reproducible. Recent work, most notably that of Dodis, Reyzin, and Smith, has shown how these obstacles may be overcome by allowing some auxiliary public information to be reliably sent from a server to the human user. Subsequent work of Boyen has shown how to extend these techniques, in the random oracle model, to enable unidirectional authentication from the user to the server without the assumption of a reliable communication channel. 
 
We show two efficient techniques enabling the use of biometric data to achieve mutual authentication or authenticated key exchange over a completely insecure (i.e., adversarially controlled) channel. In addition to achieving stronger security guarantees than the work of Boyen, we improve upon his solution in a number of other respects: we tolerate a broader class of errors and, in one case, improve upon the parameters of his solution and give a proof of security in the standard model.
7418837
Lower bounds for collusion-secure fingerprinting
Collusion-secure fingerprinting codes are an important primitive used by many digital watermarking schemes [1, 10, 9]. Boneh and Shaw [3] define a model for these types of codes and present an explicit construction. Their code has length <i>O</i>(<i>c</i><sup>3</sup> log(l/ε)) and attains security against coalitions of size <i>c</i> with ε error. Boneh and Shaw also present a lower bound of Ω (<i>c</i><sup>3</sup>log(1/<i>c</i>ε)) on the length of any collusion-secure code.We give new lower bounds on the length of collusion-secure codes by analyzing a weighted coinflipping strategy for the coalition. As an illustration of our methods, we give a simple proof that the Boneh-Shaw construction cannot be asymptotically improved. Next, we prove a general lower bound: no secure code can have length <i>O</i>(<i>c</i><sup>2</sup>1og(1/<i>c</i>ε)), which improves the previous known bound by a factor of <i>c</i>. In particular, we show that any secure code will have length Ω(<i>c</i><sup>2</sup> log(1/<i>c</i>ε)) as long as log(l/ε) ≥ <i>K</i> <i>k</i> log <i>c</i>, where <i>K</i> is a constant and <i>k</i> is the number of columns in the code (in some sense, a measure of the code's complexity). Finally, we describe a general paradigm for constructing fingerprinting codes which encompasses the construction of [3], and show that no secure code that follows this paradigm can have length <i>O</i>((c<sup>3</sup>/log c) log(1/<i>c</i>ε)) follows this (again, by showing a lower bound for large values of ln(1/ε)). This suggests that any attempts at improvement should be directed toward techniques that lie outside our paradigm.
537185
A Novel Hueristic and Provable Bounds for Reconfigurable Architecture Design
This paper is concerned with the application of formal optimisation methods to the design of mixed-granularity FPGAs. In particular, the authors investigate the appropriate mix and floorplan of heterogeneous elements: multipliers, RAMs, and LUT-based logic, in order to maximise the performance of a set of DSP benchmark applications, given a fixed silicon budget. The authors extend our previous mathematical programming framework by proposing a novel set of heuristics, capable of providing upper bounds on the achievable reconfigurable-to-fixed-logic performance ratio. The results provide, for the first time, quantifications of the optimal performance/area-enhancing capability of multipliers and RAM blocks within a system context, and indicate that only a minimal performance benefit can be achieved over Virtex II by re-organising the device floorplan, when using optimal technology mapping
7234685
Mining ChIP-chip data for transcription factor and cofactor binding sites
MOTIVATION
Identification of single motifs and motif pairs that can be used to predict transcription factor localization in ChIP-chip data, and gene expression in tissue-specific microarray data.


RESULTS
We describe methodology to identify de novo individual and interacting pairs of binding site motifs from ChIP-chip data, using an algorithm that integrates localization data directly into the motif discovery process. We combine matrix-enumeration based motif discovery with multivariate regression to evaluate candidate motifs and identify motif interactions. When applied to the HNF localization data in liver and pancreatic islets, our methods produce motifs that are either novel or improved known motifs. All motif pairs identified to predict localization are further evaluated according to how well they predict expression in liver and islets and according to how conserved are the relative positions of their occurrences. We find that interaction models of HNF1 and CDP motifs provide excellent prediction of both HNF1 localization and gene expression in liver. Our results demonstrate that ChIP-chip data can be used to identify interacting binding site motifs.


AVAILABILITY
Motif discovery programs and analysis tools are available on request from the authors.
5424518
Round Efficiency of Multi-party Computation with a Dishonest Majority
We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality and up to n - 1 of these players may be arbitrarily malicious. Previous protocols for this setting (when a broadcast channel is available) require O(n) rounds. We present two protocols with improved round complexity: The first assumes only the existence of trapdoor permutations and dense cryptosystems, and achieves round complexity O(log n) based on a proof scheduling technique of Chor and Rabin [13]; the second requires a stronger hardness assumption (along with the non-black-box techniques of Barak [2]) and achieves O(1) round complexity.