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

An efficient profile-based algorithm for scratchpad memory partitioning

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2005年第11期24卷 1660-1676页

作者： Angiolini, F Benini, L Caprara, A Univ Bologna Dipartimento Elettron Informat & Sistemist I-40136 Bologna Italy

Focusing on embedded applications, scratchpad memories (SPMs) look like a best-compromise solution when taking into account performance, energy consumption, and die area. The main challenge in SPM design is to optimally map memory locations to scratchpad locations. This paper describes an algorithm to solve such a mapping problem by means of dynamic programming applied to a synthesizable hardware architecture. The algorithm works by mapping segments of external memory to physically partitioned banks of an on-chip SPM;this architecture provides significant energy savings. The algorithm does not require any user-set bound on the number of partitions and takes into account partitioning overhead. Improving on previous solutions, execution time is polynomial in the number of memory locations, even in the most general solving policy. This has the major practical advantage of allowing an arbitrary number of scratchpad segments, something that was impossible with previous methods, whose running time is exponential to this number. Strategies to optimize memory requirements and speed of the algorithm are exploited. Additionally, we integrate this algorithm in a complete and automated design, simulation, and synthesis flow.

关键词： design automation dynamic programming embedded design memory hierarchy partitioning algorithm power saving scratchpad memory (SPM)

来源：评论

学校读者我要写书评

暂无评论

Balanced multiple description video coding using optimal partitioning of the DCT coefficients

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2005年第7期15卷 928-934页

作者： Matty, KR Kondi, LP SUNY Buffalo Univ Buffalo Dept Elect Engn Buffalo NY 14260 USA

In this paper, we propose a balanced multiple description video coding scheme which is based on the partitioning of the discrete cosine transform (DCT) coefficients. Our scheme splits the single-layered stream generated by a standard coder into two correlated and balanced (virtually identical rates and distortions) substreams. The optimization is in the redundancy-rate-distortion sense using Lagrangian relaxation for optimum allocation of redundancy among the blocks in the frame. A greedy algorithm to meet the equal distortions criterion and an algorithm to optimally achieve equal bit rates for the two descriptions are proposed. Our simulation results substantiate our claim of achieving balanced descriptions at high peak signal-to-noise ratios values for any specified redundancy and any target bit rate. Our design complies with the existing motion-compensated DCT-based standards, i.e., each description can be independently decoded by any standard decoder.

关键词： greedy algorithm H.263 multiple description coding partitioning algorithm rate distortion-theory video coding

来源：评论

学校读者我要写书评

暂无评论

An efficient partitioning algorithm for distributed virtual environment systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2002年第3期13卷 193-211页

作者： Lui, JCS Chan, MF Chinese Univ Hong Kong Dept Comp Sci & Engn Sha Tin Hong Kong Peoples R China Poly Asia Comuter Inc Kowloon Hong Kong Peoples R China

Distributed virtual environment (DVE) systems model and simulate the activities of thousands of entities interacting in a virtual world over a wide area network. Possible applications for DVE systems are multiplayer video games, military and industrial trainings, and collaborative engineering. In general, a DVE system is composed of many servers and each server is responsible to manage multiple clients who want to participate in the virtual world. Each server receives updates from different clients (such as the current position and orientation of each client) and then delivers this information to other clients in the virtual world. The server also needs to perform other tasks, such as object collision detection and synchronization control. A large scale DVE system needs to support many clients and this imposes a heavy requirement on networking resources and computational resources. Therefore, how to meet the growing requirement of bandwidth and computational resources is one of the major challenges in designing a scalable and cost-effective DVE system. In this paper, we propose an efficient partitioning algorithm that addresses the scalability issue of designing a large scale DVE system. The main idea is to dynamically divide the virtual world into different partitions and then efficiently assign these partitions to different servers. This way, each server will process approximately the same amount of workload. Another objective of the partitioning algorithm is to reduce the server-to-server communication overhead. The theoretical foundation of our dynamic partitioning algorithm is based on the linear optimization principle. We also illustrate how one can parallelize the proposed partitioning algorithm so that it can efficiently partition a very large scale DVE system. Lastly, experiments are carried out to illustrate the effectiveness of the proposed partitioning algorithm under various settings of the virtual world.

关键词： distributed virtual environment scalability issue partitioning algorithm load balancing communication reduction linear optimization

来源：评论

学校读者我要写书评

暂无评论

partitioning colored point sets into monochromatic parts

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2002年第5期12卷 401-412页

作者： Dumitrescu, A Pach, J Univ Wisconsin Milwaukee WI 53211 USA NYU Courant Inst Math Sci New York NY 10012 USA

We show that any two-colored set of n points in general position in the plane can be partitioned into at most [n+1/2] monochromatic subsets, whose convex hulls are pairwise disjoint. This bound cannot be improved in general. We present an O(n log n) time algorithm for constructing a partition into fewer parts, if the coloring is unbalanced, i.e., the sizes of the two color classes differ by more than one. The analogous question for k-colored point sets (k > 2) and its higher dimensional variant are also considered.

关键词： colored point sets partitioning algorithm matching algorithm Davenport-Schinzel sequence

来源：评论

学校读者我要写书评

暂无评论

Concurrency preserving partitioning algorithm for parallel logic simulation

引用

VLSI DESIGN 1999年第3期9卷 253-270页

作者： Kim, HK Jean, J Wright State Univ Dept Comp Sci & Engn Dayton OH 45435 USA

A partitioning algorithm for parallel discrete event gate-level logic simulations is proposed in this paper. Unlike most other partitioning algorithms, the proposed algorithm preserves computation concurrency by assigning to processors circuit gates that can be evaluated at about the same time. As a result, the improved concurrency preserving partitioning (iCPP) algorithm can provide better load balancing throughout the period of a parallel simulation. This is especially important when the algorithm is used together with a Time Warp simulation where a high degree of concurrency can lead to fewer rollbacks and better performance. The algorithm consists of three phases and three conflicting goals can be separately considered so to reduce computational complexity. To evaluate the quality of partitioning algorithms in terms of preserving concurrency, a concurrency metric that requires neither sequential nor parallel simulation is proposed. A levelization technique is used in computing the metric so to determine gates which can be evaluated at about the same time. A parallel gate-level logic simulator is implemented on an INTEL Paragon and an IBM SP2 to evaluate the performance of the iCPP algorithm. The results are compared with several other partitioning algorithms to show that the iCPP algorithm does preserve concurrency pretty well and reasonable speedup may be achieved with the algorithm.

关键词： parallel logic simulation partitioning algorithm discrete event simulation concurrency load balancing time warp

来源：评论

学校读者我要写书评

暂无评论

块循环矩阵方程组的新算法

引用

高等学校计算数学学报 2001年第3期23卷 281-288页

作者：张耀明山东理工大学数理系淄博255012

A kind of new partitioning algorithm that solves the linear equation system with block cycle coefficient matrix is presented in this paper. The original problem is partitioned into a series of independent subproblems. Compared with the original problem, the dimension of all these subproblems are vary small. This point ensures that it have a better conditioning and give smaller round-off errors. More importantly, the technique leads to a higher efficiency of computation.

关键词： block cycle matrix block cycle matrix equation system partitioning algorithm

来源：评论

学校读者我要写书评

暂无评论

Stochastic analysis of partitioning algorithms for matching problems

引用

JOURNAL OF APPLIED PROBABILITY 2000年第2期37卷 494-503页

作者： Rüschendorf, L Sachs, G Univ Freiburg Inst Math Stochast D-79104 Freiburg Germany

partitioning algorithms for the Euclidean matching and for the semi-matching problem in the plane are introduced and analysed. The algorithms are analogues of Karp's well-known dissection algorithm for the travelling salesman problem. The algorithms are proved to run in time n log n and to approximate the optimal matching in the probabilistic sense. The analysis is based on the techniques developed in Karp (1977) and on the limit theorem of Redmond and Yukich (1993) for quasiadditive functionals.

关键词： matching problem partitioning algorithm quasiadditive functional

来源：评论

学校读者我要写书评

暂无评论

The refinement-tree partition for parallel solution of partial differential equations

引用

JOURNAL OF RESEARCH OF THE NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY 1998年第4期103卷 405-414页

作者： Mitchell, WF Natl Inst Stand & Technol Gaithersburg MD 20899 USA

Dynamic load balancing is considered in the context of adaptive multilevel methods for partial differential equations on distributed memory multiprocessors. An approach that periodically repartitions the grid is taken. The important properties of a partitioning algorithm are presented and discussed in this context. A partitioning algorithm based on the refinement tree of the adaptive grid is presented and analyzed in terms of these properties. Theoretical and numerical results are given.

关键词： partitioning algorithm partial differential equations refinement tree partitions

来源：评论

学校读者我要写书评

暂无评论

A classification algorithm of 3D volumetric data for hierarchical visualization

A classification algorithm of 3D volumetric data for hierarc...

引用

Conference on Input/Output and Imaging Technologies

作者： Sato, M Liu, Y Takahashi, H Nakajima, M Tokyo Inst Technol Grad Sch Informat Sci & Engn Meguro Ku Tokyo 1528552 Japan

ISBN: (纸本)0819428760

This paper presents one part of our work on "hierarchical visualization." Here, we propose an efficient hierarchical structure for the visualization of 3D volumetric data, where for instance, data compression techniques are embedded into the hierarchical structure. The hierarchical structure consists of two layers. The first hierarchy roughly visualizes the whole lossy compressed data so that we can quickly understand and interpret the outline of the whole 3D volumetric dataset. This step allows users to choose the desired parts of the 3D volumetric data. The second hierarchy is used for scrutinizing the detail of the chosen parts using lossless compressed data. To implement the hierarchical structure we propose a partitioning algorithm for 3D volumetric data based on principal component analysis. With principal component analysis, the original 3D volumetric space can be divided into a number of 3D volumetric blocks such that each block contains similar data. Analyzing these specific blocks and taking advantage of an octree hierarchy, from the whole 3D volumetric dataset we can easily access only the parts which are required for display. The proposed partitioning algorithm should be very useful in reducing the amount of rendering, which means that we will need only to precisely render the blocks required for display, and not the whole 3D volumetric dataset.

关键词： 3D medical volume visualization hierarchical visualization partitioning algorithm octree

来源：评论

学校读者我要写书评

暂无评论

Performance analysis of re-configurable partitioned TLBs

Performance analysis of re-configurable partitioned TLBs

引用

30th Hawaii International Conference on System Sciences (HICSS 30)

作者： Channon, D Koch, D Univ Newcastle Dept Comp Sci & Software Engn Newcastle NSW 2308 Australia

ISBN: (纸本)0818677430

Conventional address translation mechanisms generally use a translation lookaside buffer cache (TLB) of current page translations to provide virtual to physical page addressing. This translation cache is generally shared amongst all processes, and between reference types irrespective as to whether they relate to instruction or data references. In this paper we introduce a reconfigurable partitioned TLB which improves TLB performance by removing cache conflict misses between the distinct reference types. Extensive simulations using selected SPEC95 workloads show that data reference translations unfairly compete with instruction reference translations by dominating a standard shared TLB. We compare the traditional shared TLB with both fixed partition and re-configurable fixed partition TLB structures that segregate instruction and data page translation entries. We show that the partitioned TLB operates optimally when the miss ratio of the instruction reference partition is maintained at a lower level than the miss radio for the data reference? partition. By dynamically preserving a balance between the translation performance Of instruction and data components, a protected 'working set' of instruction translation entries can be maintained. This can be achieved within the one TLB structure with soft partitions separating reference types.

关键词： computer architecture memory management address translation partitioning algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：