The codesign of processor hardware, software, and algorithms for a video processor is investigated. The case study focuses on the Inverse Discrete Cosine Transform (IDCT) of an MPEG-1 decoder. Variations of the IDCT a...
详细信息
The codesign of processor hardware, software, and algorithms for a video processor is investigated. The case study focuses on the Inverse Discrete Cosine Transform (IDCT) of an MPEG-1 decoder. Variations of the IDCT algorithm on different processors are compared. The paper describes a codesign methodology that is based on automatic quantitative analysis. The automation makes complex explorations for specific application domains feasible. Performance results are presented for variations of the algorithms, for different compiler techniques, and for increasing the instruction-level parallelism of the underlying processor hardware. In particular, the synergy effect obtained from the combined effort of these different fields is investigated.
The authors point out that, in one-dimensional (1-D) recursive median (RM) filtering, all of the previous outputs except the most recent output are redundant in determining the present output. On the basis of this obs...
详细信息
The authors point out that, in one-dimensional (1-D) recursive median (RM) filtering, all of the previous outputs except the most recent output are redundant in determining the present output. On the basis of this observation, efficient software and VLSI algorithms for 1-D RM filters are presented. It is shown that the implementation of RM filtering based on the proposed algorithms is simpler than that of standard median filtering.< >
Search-based graph queries, such as finding short paths and isomorphic subgraphs, are dominated by memory latency. If input graphs can be partitioned appropriately, large cluster-based computing platforms can run thes...
详细信息
Search-based graph queries, such as finding short paths and isomorphic subgraphs, are dominated by memory latency. If input graphs can be partitioned appropriately, large cluster-based computing platforms can run these queries. However, the lack of compute-bound processing at each vertex of the input graph and the constant need to retrieve neighbors implies low processor utilization. Furthermore, graph classes such as scale-free social networks lack the locality to make partitioning clearly effective. Massive multithreading is an alternative architectural paradigm, in which a large shared memory is combined with processors that have extra hardware to support many thread contexts. The processor speed is typically slower than normal, and there is no data cache. Rather than mitigating memory latency, multithreaded machines tolerate it. This paradigm is well aligned with the problem of graph search, as the high ratio of memory requests to computation can be tolerated via multithreading. In this paper, we introduce the multithreaded graph library (MTGL), generic graph query software for processing semantic graphs on multithreaded computers. This library currently runs on serial machines and the Cray MTA-2, but Sandia is developing a run-time system that will make it possible to run MTGL-based code on symmetric multiprocessors. We also introduce a multithreaded algorithm for connected components and a new heuristic for inexact subgraph isomorphism We explore the performance of these and other basic graph algorithms on large scale-free graphs. We conclude with a performance comparison between the Cray MTA-2 and Blue Gene/Light for s-t connectivity.
A crucial step in understanding a large legacy software system is to decompose it into meaningful subsystems, which can be separately studied. This decomposition can be done either manually or automatically by a softw...
详细信息
A crucial step in understanding a large legacy software system is to decompose it into meaningful subsystems, which can be separately studied. This decomposition can be done either manually or automatically by a software clustering algorithm (SCA). Similar versions of a software system can be expected to have similar decompositions. We say an SCA is stable if small changes in its input (the software system) produce small changes in its output (the decomposition). The paper defines stability formally, explains why it is an essential property for an SCA, and gives experimental results from evaluating the stability of various decomposition algorithms suggested in the literature.
Collections of general purpose networked workstations offer processing capability that often rivals or exceeds supercomputers. Since networked workstations are readily available in most organizations, they provide an ...
详细信息
Collections of general purpose networked workstations offer processing capability that often rivals or exceeds supercomputers. Since networked workstations are readily available in most organizations, they provide an economic and scalable alternative to parallel machines. The authors discuss how individual nodes in a computer network can be used as a collection of connected processing elements to improve the performance of a software engineering tool that we developed. Our tool, called Bunch, automatically clusters the structure of software systems into a hierarchy of subsystems. Clustering helps developers understand complex systems by providing them with high-level abstract (clustered) views of the software structure. The algorithms used by Bunch are computationally intensive and, hence, we would like to improve our tool's performance in order to cluster very large systems. The paper describes how we designed and implemented a distributed version of Bunch, which is useful for clustering large systems.
The authors deal with the problems of software partition for distributed real-time applications. The software-partitioning models analyzed are those that take maximizing the efficiency in resource utilization for thei...
详细信息
ISBN:
(纸本)0897912586
The authors deal with the problems of software partition for distributed real-time applications. The software-partitioning models analyzed are those that take maximizing the efficiency in resource utilization for their objective, while observing the constraints on CPU throughput, memory space available, maximally allowed task execution time, and the order of module execution. The problem of software partition based on the models is proved to be NP-complete. There is no efficient partitioning algorithm for the models. The authors present two heuristic software-partitioning algorithms.< >
Nowadays, the problem of fixing soils in construction is very relevant. Jet grouting is one of the most effective methods of soil stabilization. This injection method allows you to create a geotechnical screen and sig...
详细信息
ISBN:
(数字)9781728181790
ISBN:
(纸本)9781728181806
Nowadays, the problem of fixing soils in construction is very relevant. Jet grouting is one of the most effective methods of soil stabilization. This injection method allows you to create a geotechnical screen and significantly reduce the subsidence of the base. This technology is widely used both in Russia and abroad due to economic, environmental feasibility and technical efficiency. This article describes the algorithm the automation of the design process when the technological strengthening of soil grouting piles in the tunnel about space. On the basis of the developed algorithm was created by the application software for AutoCAD system, which is usually developed project documentation.
Decomposing source code components and relations into subsystem clusters is an active area of research. Numerous clustering approaches have been proposed in the reverse engineering literature, each one using a differe...
详细信息
Decomposing source code components and relations into subsystem clusters is an active area of research. Numerous clustering approaches have been proposed in the reverse engineering literature, each one using a different algorithm to identify subsystems. Since different clustering techniques may not produce identical results when applied to the same system, mechanisms that can measure the extent of these differences are needed. Some work to measure the similarity between decompositions has been done, but this work considers the assignment of source code components to clusters as the only criterion for similarity. We argue that better similarity measurements can be designed if the relations between the components are considered. The authors propose two similarity measurements that overcome certain problems in existing measurements. We also provide some suggestions on how to identify and deal with source code components that tend to contribute to poor similarity results. We conclude by presenting experimental results, and by highlighting some of the benefits of our similarity measurements.
The evolution of the definition of the notion "algorithm" is considered, and four ways to the interpretation of algorithm are given. The last mentioned concerns the computer solving of problems. The software...
详细信息
The evolution of the definition of the notion "algorithm" is considered, and four ways to the interpretation of algorithm are given. The last mentioned concerns the computer solving of problems. The software/hardware model of algorithm (SH-model), which specifies the notion of algorithm concerning computer devices, is formally defined. The list of properties of algorithm is expanded. The hardware and structural complexities are added to the list of properties. software and structural complexities are defined as an amount of information, which is included into computer devices.
We propose a novel approach for evaluating software clustering algorithms in the context of program comprehension. Based on the assumption that program comprehension is a task-driven activity, our approach utilizes in...
详细信息
ISBN:
(纸本)9781467330909
We propose a novel approach for evaluating software clustering algorithms in the context of program comprehension. Based on the assumption that program comprehension is a task-driven activity, our approach utilizes interaction logs from previous maintenance sessions to automatically devise multiple comprehension-aware and task-sensitive decompositions of software systems. These decompositions are then used as authoritative figures to evaluate the effectiveness of various clustering algorithms. Our approach addresses several challenges associated with evaluating clustering algorithms externally using expert-driven authoritative decompositions. Such limitations include the subjectivity of human experts, the availability of such authoritative figures, and the decaying structure of software systems. We conduct an experimental analysis using two datasets, including an open-source system and a proprietary system, to test the applicability of our approach and validate our research claims.
暂无评论