Catálogo de publicaciones - revistas

<jats:p>The Parallel Random Access Machine (PRAM) is an abstract model of parallel computation which allows researchers to focus on the essential characteristics of a parallel architecture and ignore other details. The PRAM has long been acknowledged to be a useful tool for the study of parallel computing, but unfortunately it is not physically implementable in hardware. In order to take advantage of the broad base of algorithms and results regarding this high-level abstraction one needs general methods for allowing the execution of PRAM algorithms on more realistic machines. In the following we survey these methods, which we refer to as PRAM simulation techniques. The general issues of memory management and routing are discussed, and both randomized and deterministic solutions are considered. We show that good theoretical solutions to many of the subproblems in PRAM simulation have been developed, though questions still exist as to their practical utility. This article should allow those performing research in this field to become well acquainted with the current state of the art, while allowing the novice to get an intuitive feeling for the fundamental questions being considered. The introduction should provide a concise tutorial for those unfamiliar with the problem of PRAM simulation.</jats:p>

<jats:p>An organized record of actual flaws can be useful to computer system designers, programmers, analysts, administrators, and users. This survey provides a taxonomy for computer program security flaws, with an Appendix that documents 50 actual security flaws. These flaws have all been described previously in the open literature, but in widely separated places. For those new to the field of computer security, they provide a good introduction to the characteristics of security flaws and how they can arise. Because these flaws were not randomly selected from a valid statistical sample of such flaws, we make no strong claims concerning the likely distribution of actual security flaws within the taxonomy. However, this method of organizing security flaw data can help those who have custody of more representative samples to organize them and to focus their efforts to remove and, eventually, to prevent the introduction of security flaws.</jats:p>

<jats:p>Fast, efficient logic simulators are an essential tool in modern VLSI system design. Logic simulation is used extensively for design verification prior to fabrication, and as VLSI systems grow in size, the execution time required by simulation is becoming more and more significant. Faster logic simulators will have an appreciable economic impact, speeding time to market while ensuring more thorough system design testing. One approach to this problem is to utilize parallel processing, taking advantage of the concurrency available in the VLSI system to accelerate the logic simulation task.</jats:p> <jats:p>Parallel logic simulation has received a great deal of attention over the past several years, but this work has not yet resulted in effective, high-performance simulators being available to VLSI designers. A number of techniques have been developed to investigate performance issues: formal models, performance modeling, empirical studies, and prototype implementations. Analyzing reported results of these techniques, we conclude that five major factors affect performance: synchronization algorithm, circuit structure, timing granularity, target architecture, and partitioning. After reviewing techniques for parallel simulation, we consider each of these factors using results reported in the literature. Finally we synthesize the results and present directions for future research in the field.</jats:p>

<jats:p>Parallelizing logic programming has attracted much interest in the research community, because of the intrinsic OR- and AND-parallelisms of logic programs. One research stream aims at transparent exploitation of parallelism in existing logic programming languages such as Prolog, while the family of concurrent logic languages develops language constructs allowing programmers to express the concurrency—that is, the communication and synchronization between parallel processes—within their algorithms. This article concentrates mainly on transparent exploitation of parallelism and surveys the most mature solutions to the problems to be solved in order to obtain efficient implementations. These solutions have been implemented, and the most efficient parallel logic programming systems reach effective speedups over state-of-the-art sequential Prolog implementations. The article also addresses current and prospective research issues in extending the applicability and the efficiency of existing systems, such as models merging the transparent parallelism and the concurrent logic languages approaches, combination of constraint logic programming with parallelism, and use of highly parallel architectures.</jats:p>

<jats:p>In the last three decades a large number of compiler transformations for optimizing programs have been implemented. Most optimizations for uniprocessors reduce the number of instructions executed by the program using transformations based on the analysis of scalar quantities and data-flow techniques. In contrast, optimizations for high-performance superscalar, vector, and parallel processors maximize parallelism and memory locality with transformations that rely on tracking the properties of arrays using loop dependence analysis.</jats:p> <jats:p>This survey is a comprehensive overview of the important high-level program restructuring techniques for imperative languages, such as C and Fortran. Transformations for both sequential and various types of parallel architectures are covered in depth. We describe the purpose of each transformation, explain how to determine if it is legal, and give an example of its application.</jats:p> <jats:p>Programmers wishing to enhance the performance of their code can use this survey to improve their understanding of the optimizations that compilers can perform, or as a reference for techniques to be applied manually. Students can obtain an overview of optimizing compiler technology. Compiler writers can use this survey as a reference for most of the important optimizations developed to date, and as bibliographic reference for the details of each optimization. Readers are expected to be familiar with modern computer architecture and basic program compilation techniques.</jats:p>

<jats:p> In geometric range searching, algorithmic problems of the following type are considered. Given an <jats:italic>n</jats:italic> -point set P in the plane, build a data structure so that, given a query triangle R, the number of points of P lying in R can be determined quickly. Similar questions can be asked for point sets in higher dimensions, with triangles replaced by simplices or by more complicated shapes. Algorithms of this type are of crucial importance in computational geometry, as they can be used as subroutines in solutions to many seemingly unrelated problems, which are often motivated by practical applications, for instance in computer graphics (ray tracing, hidden-surface removal etc.). We present a survey of theoretical results and the main techniques in geometric range searching. </jats:p>