检索结果-内蒙古大学图书馆

Efficient synthesis of out-of-core algorithms using a nonlinear optimization solver

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2006年第5期66卷 659-673页

作者： Krishnan, S Krishnamoorthy, S Baumgartner, G Lam, CC Ramanujam, J Sadayappan, P Choppella, V Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA Louisiana State Univ Dept Elect & Comp Engn Baton Rouge LA USA Indian Inst Informat Technol & Management Thiruvananthapuram 695581 Kerala India

We address the problem of efficient out-of-core code generation for a special class of imperfectly nested loops encoding tensor contractions arising in quantum chemistry computations. These loops operate on arrays too large to fit in physical memory. The problem involves determining optimal tiling of loops and placement of disk I/O statements. This entails a search in an explosively large parameter space. We formulate the problem as a nonlinear optimization problem and use a discrete constraint solver to generate optimized out-of-core code. The solution generated using the discrete constraint solver consistently outperforms other approaches by up to a factor of four. Measurements on sequential and parallel versions of the generated code demonstrate the effectiveness of the approach. (c) 2005 Published by Elsevier Inc.

关键词： data locality optimization out-of-core algorithms program transformation compiler optimization discrete constrained search tensor contractions

来源：评论

学校读者我要写书评

暂无评论

A Runtime System for Programming out-of-core Matrix algorithms-by-Tiles on Multithreaded Architectures

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2012年第4期38卷 25-25页

作者： Quintana-Orti, Gregorio Igual, Francisco D. Marques, Mercedes Quintana-Orti, Enrique S. van de Geijn, Robert A. Univ Jaume 1 Dept Ingn & Ciencia Comp Castellon de La Plana 12071 Spain Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

out-of-core implementations of algorithms for dense matrix computations have traditionally focused on optimal use of memory so as to minimize I/O, often trading programmability for performance. In this article we show how the current state of hardware and software allows the programmability problem to be addressed without sacrificing performance. This comes from the realizations that memory is cheap and large, making it less necessary to optimally orchestrate I/O, and that new algorithms view matrices as collections of submatrices and computation as operations with those submatrices. This enables libraries to be coded at a high level of abstraction, leaving the tasks of scheduling the computations and data movement in the hands of a runtime system. This is in sharp contrast to more traditional approaches that leverage optimal use of in-core memory and, at the expense of introducing considerable programming complexity, explicit overlap of I/O with computation. Performance is demonstrated for this approach on multicore architectures as well as platforms equipped with hardware accelerators.

关键词： algorithms Performance High-performance libraries linear algebra multithreaded architectures out-of-core algorithms

来源：评论

学校读者我要写书评

暂无评论

Single-pass top-N subgraph centrality of graphs via subspace projections

引用

JOURNAL OF COMPLEX NETWORKS 2025年第1期13卷

作者： Kalantzis, Vassilis Kollias, Georgios Ubaru, Shashanka Abe, Naoki Horesh, Lior IBM Res Thomas J Watson Res Ctr 1101 Kitchawan Rd Yorktown Hts NY 10598 USA

Subgraph centrality is a widely used centrality measure to rank the the importance of vertices in graphs. Due to the cubic cost of matrix diagonalization, subgraph centrality scores are typically approximated via projection onto an invariant subspace computed by a Krylov subspace eigenvalue solver. However, for dynamically evolving graphs or graphs whose corresponding adjacency matrix does not fit in the system memory, the application of memory-bound Krylov subspace eigenvalue solvers can be expensive. In this paper, we propose an algorithm to approximately identify the most influential nodes of networks under the constraint that each entry of the corresponding adjacency matrix is loaded only once. To achieve this, the algorithm parses the graph one subgraph at a time and accumulates previously processed graph information via updating a partial spectral factorization through a Rayleigh-Ritz projection. Several options to set the Rayleigh-Ritz subspace are discussed while numerical experiments performed on real-world graph datasets verify the effectiveness of the proposed algorithm. In particular, one of the approaches discussed in this paper incurs only linear complexity with respect to the update size.

关键词： subgraph centralities Estrada index out-of-core algorithms top-N recommendation Lanczos

来源：评论

学校读者我要写书评

暂无评论

out-OF-core IMPLEMENTATIONS OF CHOLESKY FACTORIZATION: LOOP-BASED VERSUS RECURSIVE algorithms

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2008年第4期30卷 1302-1319页

作者： Bereux, Natacha Ecole Polytech CNRS CMAP F-91128 Palaiseau France

We compare, in the same framework, out-of-core implementations of the Cholesky factorization algorithm. The candidate implementations are the classical blocked left-looking variant and a more recent recursive formulation. Both have been implemented for real positive definite matrices: the former in the parallel out-of-core linear algebra package (POOCLAPACK) library and the latter in the scalable out-of-core linear algebra computations (SOLAR) library. We perform a theoretical analysis of the amount of input/output (I/O) operations required by each variant. We consider alternatives for the left-looking algorithm: the one-tile and two-tiles approaches. We show that when main memory is restricted, the one-tile approach yields less I/O volume. We then show that the left-looking implementation requires less I/O volume than the recursive variant. We have implemented all for complex matrices, and we report on numerical experiments.

关键词： Cholesky factorization out-of-core algorithms

来源：评论

学校读者我要写书评

暂无评论

out-of-core streamline visualization on large unstructured meshes

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 1997年第4期3卷 370-380页

作者： Ueng, SK Sikorski, C Ma, KL Natl Taiwan Ocean Univ Dept Comp Sci Chilung Taiwan Univ Utah Dept Comp Sci Salt Lake City UT 84112 USA NASA Langley Res Ctr Inst Comp Appl Sci & Engn Hampton VA 23861 USA

This paper presents an out-of-core approach for interactive streamline construction on large unstructured tetrahedral meshes containing millions of elements. The out-of-core algorithm uses an octree to partition and restructure the raw data into subsets stored into disk flies for fast data retrieval. A memory management policy tailored to the streamline calculations is used such that, during the streamline construction, only a very small amount of data are brought into the main memory on demand. By carefully scheduling computation and data fetching, the overhead of reading data from the disk is significantly reduced and good memory performance results. This out-of-core algorithm makes possible interactive streamline visualization of large unstructured-grid data sets on a single mid-range workstation with relatively low main-memory capacity: 5-15 megabytes. We also demonstrate that this approach is much more efficient than relying on virtual memory and operating system's paging algorithms.

关键词： streamline visualization interactive techniques unstructured meshes computational fluid dynamics out-of-core algorithms memory management disk management

来源：评论

学校读者我要写书评

暂无评论

Quick-VDR: out-of-core view-dependent rendering of gigantic models

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2005年第4期11卷 369-382页

作者： Yoon, SE Salomon, B Gayle, R Manocha, D Univ N Carolina Dept Comp Sci Chapel Hill NC 27599 USA

We present a novel approach for interactive view-dependent rendering of massive models. Our algorithm combines view-dependent simplification, occlusion culling, and out-of-core rendering. We represent the model as a clustered hierarchy of progressive meshes (CHPM). We use the cluster hierarchy for coarse-grained selective refinement and progressive meshes for fine-grained local refinement. We present an out-of-core algorithm for computation of a CHPM that includes cluster decomposition, hierarchy generation, and simplification. We introduce novel cluster dependencies in the preprocess to generate crack-free, drastic simplifications at runtime. The clusters are used for LOD selection, occlusion culling, and out-of-core rendering. We add a frame of latency to the rendering pipeline to fetch newly visible clusters from the disk and avoid stalls. The CHPM reduces the refinement cost of view-dependent rendering by more than an order of magnitude as compared to a vertex hierarchy. We have implemented our algorithm on a desktop PC. We can render massive CAD, isosurface, and scanned models, consisting of tens or a few hundred million triangles at 15-35 frames per second with little loss in image quality.

关键词： interactive display view-dependent rendering occlusion culling external-memory algorithm out-of-core algorithms levels-of-detail

来源：评论

学校读者我要写书评

暂无评论

Terrain simplification simplified: A general framework for view-dependent out-of-core visualization

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2002年第3期8卷 239-254页

作者： Lindstrom, P Pascucci, V Lawrence Livermore Natl Lab Livermore CA 94551 USA

This paper describes a general framework for out-of-core rendering and management of massive terrain surfaces. The two key components of this framework are: view-dependent refinement of the terrain mesh and a simple scheme for organizing the terrain data to improve coherence and reduce the number of paging events from external storage to main memory. Similar to several previously proposed methods for view-dependent refinement, we recursively subdivide a triangle mesh defined over regularly gridded data using longest-edge bisection. As part of this single, per-frame refinement pass, we perform triangle stripping, view frustum culling, and smooth blending of geometry using geomorphing. Meanwhile, our refinement framework supports a large class of error metrics, is highly competitive in terms of rendering performance, and is surprisingly simple to implement. Independent of our refinement algorithm, we also describe several data layout techniques for providing coherent access to the terrain data. By reordering the data in a manner that is more consistent with our recursive access pattern, we show that visualization of gigabyte-size data sets can be realized even on low-end, commodity PCs without the need for complicated and explicit data paging techniques. Rather, by virtue of dramatic improvements in multilevel cache coherence, we rely on the built-in paging mechanisms of the operating system to perform this task. The end result is a straightforward, simple-to-implement, pointerless indexing scheme that dramatically improves the data locality and paging performance over conventional matrix-based layouts.

关键词： terrain visualization surface simplification view-dependent refinement continuous levels of detail edge bisection error metrics geomorphing out-of-core algorithms external memory paging data layouts

来源：评论

学校读者我要写书评

暂无评论

VOLUME VISUALIZATION FOR out-OF-core 3D IMAGES BASED ON SEMI-ADAPTIVE PARTITIONING

VOLUME VISUALIZATION FOR OUT-OF-CORE 3D IMAGES BASED ON SEMI...

引用

IEEE International Conference on Image Processing (ICIP)

作者： Xue, Jian Lue, Ke Univ Chinese Acad Sci Coll Engn & Informat Technol Beijing Peoples R China

ISBN: (纸本)9781479983391

Volume rendering techniques have been used widely for high quality visualization of 3D datasets, especially 3D images. However, when rendering very large (out-of-core) datasets, some traditional in-core volume rendering algorithms do not work due to the impossibility of fitting the entire input data in the main memory of a computer. Their simple out-of-core versions do not perform well either because of the slow speed external memory access overhead. In order to solve this problem, a semi-adaptive partitioning strategy and an efficient out-of-core volume rendering method based on it are proposed in this paper. By this new partitioning strategy, the out-of-core dataset is divided into small sub-blocks in different sizes, which are organized by a BSP tree. Each sub-block can be loaded into the fast texture memory of the graphics hardware and be rendered by certain volume rendering algorithm based on 3D texture. Then the final result is obtained by composing the projection images of all the sub-blocks from back to front after traveling the BSP tree according to the viewpoint position. The experimental results indicate that the new method is effective and efficient for the volume visualization of out-of-core 3D images.

关键词： 3D image processing scientific visualization volume rendering out-of-core algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive TetraPuzzles: Efficient out-of-core construction and visualization of gigantic multiresolution polygonal models

Adaptive TetraPuzzles: Efficient out-of-core construction an...

引用

Annual Symposium of the ACM SIGGRAPH

作者： Cignoni, P Ganovelli, F Gobbetti, E Marton, F Ponchio, F Scopigno, R CNR ISTI I-56124 Pisa Italy CRS4 I-09010 Pula Italy

We describe an efficient technique for out-of-core construction and accurate view-dependent visualization of very large surface models. The method uses a regular conformal hierarchy of tetrahedra to spatially partition the model. Each tetrahedral cell contains a precomputed simplified version of the original model, represented using cache coherent indexed strips for fast rendering. The representation is constructed during a fine-to-coarse simplification of the surface contained in diamonds (sets of tetrahedral cells sharing their longest edge). The construction preprocess operates out-of-core and parallelizes nicely. Appropriate boundary constraints are introduced in the simplification to ensure that all conforming selective subdivisions of the tetrahedron hierarchy lead to correctly matching surface patches. For each frame at runtime, the hierarchy is traversed coarse-to-fine to select diamonds of the appropriate resolution given the view parameters. The resulting system can interatively render high quality Views Of out-of-core models of hundreds of millions of triangles at over 40Hz (or 70M triangles/s) on current commodity graphics platforms.

关键词： out-of-core algorithms level of detail

来源：评论

学校读者我要写书评

暂无评论

out-of-core construction and 3D visualization of level-of-detail terrains populated with large collection of heterogeneous objects

Out-of-core construction and 3D visualization of level-of-de...

引用

1st International Conference on Computer Graphics Theory and Applications (GRAPP 2006)

作者： Agrawal, Anupam Radhakrishna, M. Joshi, R. C. Deemed Univ Indian Inst Informat Technol Allahabad 211012 Uttar Pradesh India Indian Inst Technol Dept Elect & Comp Engn Roorkee 247667 Uttar Pradesh India

ISBN: (纸本)9728865392

Interactive visualization of very large-scale terrain data in scientific visualization, GIS or simulation and training applications is a hard problem. The grid digital terrain elevation and texture data are not only too large to be rendered in real-time but also exceed physical main memory capacity. Therefore out-of-core management of digital terrain data is an essential requirement. Further to bring photorealism in visualization, it is required to place multiple collections of man-made objects such as buildings, lampposts etc. as well as natural objects such as trees, grass etc. on top of the terrain surface. In this paper we have proposed an integrated approach for effective out-of-core visualization of terrains populated with large collection of static heterogeneous objects. We have developed an efficient tile-based out-of-core view-dependent Level of Detail (LOD) mesh simplification algorithm for real-time rendering of large terrains. Instead of manipulating individual triangles, the algorithm operates on clusters of geometry called blocks of aggregate triangles. Hence the amount of work CPU must perform is greatly reduced. The formation of long triangle strips for LOD blocks also solves the CPU-to-Card bandwidth problem. The tile-based multiresolution terrain geometry framework has been extended to support large satellite or aerial imagery textures. To display large collection of objects over the terrain while maintaining the real-time frame rate, an efficient object handling method has been proposed using paging technique and object instantiation. User is allowed to control the objects locations, scales and orientations. The algorithms have been implemented using Visual C++ and OpenGL 3D API and successfully tested on different real-world height maps and satellite phototextures of sizes upto 16K* 16K coupled with thousands of static objects on PCs.

关键词： terrain visualization out-of-core algorithms multiresolution modeling view-dependent refinement

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：