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

dynamic data structures for a direct search algorithm

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2002年第1期23卷 5-25页

作者： He, J Watson, LT Ramakrishnan, N Shaffer, CA Verstak, A Jiang, J Bae, K Tranter, WH Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA Virginia Polytech Inst & State Univ Dept Math Blacksburg VA 24061 USA Virginia Polytech Inst & State Univ Bradley Dept Elect & Comp Engn Blacksburg VA 24061 USA

The DIRECT (DIviding RECTangles) algorithm of Jones, Perttunen, and Stuckman (Journal of Optimization Theory and Applications, vol. 79, no. 1, pp. 157-181, 1993), a variant of Lipschitzian methods for bound constrained global optimization, has proved effective even in higher dimensions. However, the performance of a DIRECT implementation in real applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice, since it is difficult to predict memory resource requirements in advance. This is especially critical in multidisciplinary engineering design applications, where the DIRECT optimization is just one small component of a much larger computation, and any component failure aborts the entire design process. To make the DIRECT global optimization algorithm efficient and robust on large-scale, multidisciplinary engineering problems, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus of this paper is on design issues of the dynamic data structures, and related memory management strategies. Numerical computing techniques and modifications of Jones' original DIRECT algorithm in terms of stopping rules and box selection rules are also explored. Performance studies are done for synthetic test problems with multiple local optima. Results for application to a site-specific system simulator for wireless communications systems ((SW)-W-4) are also presented to demonstrate the effectiveness of the proposed dynamic data structures for an implementation of DIRECT.

关键词： global optimization DIRECT algorithm direct search dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

I/O-efficient dynamic planar point location

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2004年第2期29卷 147-162页

作者： Arge, L Vahrenhold, J Duke Univ Dept Comp Sci Durham NC 27708 USA Univ Munster Inst Informat D-48149 Munster Germany

We present an I/O-efficient dynamic data structure for point location in a general planar subdivision. Our structure uses O(N/B) disk blocks of size B to store a subdivision of size N. Queries can be answered in O(log(B)(2) N) I/Os in the worst-case, and insertions and deletions can be performed in O(log(B)(2) N) and O(log(B) N) I/Os amortized, respectively. Part of our data structure is based on an external version of the so-called logarithmic method that allows for efficient dynamization of static external-memory data structures with certain characteristics. Another important part of our structure is an external data structure for vertical ray-shooting among line segments in the plane with endpoints on rootB + 1 vertical lines, developed using an external version of dynamic fractional cascading. We believe that these methods could prove helpful in the development of other dynamic external memory data structures. (C) 2004 Elsevier B.V. All rights reserved.

关键词： point location I/O efficient external memory dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Hazard pointers: Safe memory reclamation for lock-free objects

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2004年第6期15卷 491-504页

作者： Michael, MM IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

Lock-free objects offer significant performance and reliability advantages over conventional lock-based objects. However, the lack of an efficient portable lock-free method for the reclamation of the memory occupied by dynamic nodes removed from such objects is a major obstacle to their wide use in practice. This paper presents hazard pointers, a memory management methodology that allows memory reclamation for arbitrary reuse. It is very efficient, as demonstrated by our experimental results. It is suitable for user-level applications-as well as system programs-without dependence on special kernel or scheduler support. It is wait-free. It requires only single-word reads and writes for memory access in its core operations. It allows reclaimed memory to be returned to the operating system. In addition, it offers a lock-free solution for the ABA problem using only practical single-word instructions. Our experimental results on a multiprocessor system show that the new methodology offers equal and, more often, significantly better performance than other memory management methods, in addition to its qualitative advantages regarding memory reclamation and independence of special hardware support. We also show that lock-free implementations of important object types, using hazard pointers, offer comparable performance to that of efficient lock-based implementations under no contention and no multiprogramming, and outperform them by significant margins under moderate multiprogramming and/or contention, in addition to guaranteeing continuous progress and availability, even in the presence of thread failures and arbitrary delays.

关键词： lock-free synchronization concurrent programming memory management multiprogramming dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Semi-online maintenance of geometric optima and measures

引用

SIAM JOURNAL ON COMPUTING 2003年第3期32卷 700-716页

作者： Chan, TM Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

We give the first nontrivial worst-case results for dynamic versions of various basic geometric optimization and measure problems under the semi-online model, where during the insertion of an object we are told when the object is to be deleted. Problems that we can solve with sublinear update time include the Hausdorff distance of two point sets, discrete 1-center, largest empty circle, convex hull volume in three dimensions, volume of the union of axis-parallel cubes, and minimum enclosing rectangle. The decision versions of the Hausdorff distance and discrete 1-center problems can be solved fully dynamically. Some applications are mentioned.

关键词： computational geometry dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Collision detection optimization in a multi-particle system

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2003年第4期13卷 279-301页

作者： Gavrilova, ML Rokne, J Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada

Collision detection optimization in an event-driven simulation of a multi-particle system is one of the crucial tasks, determining the efficiency of the simulation. We present the event-driven simulation algorithm that employs dynamic computational geometry data structures as a tool for collision detection optimization (CDO). The first successful application of the dynamic generalized Voronoi diagram method for collision detection optimization in a system of moving particles is discussed. A comprehensive comparision of four kinetic data structures in d-dimensional space, performed in a framework of an event-driven simulation of a granular-type materials system, is supported by the experimental results.

关键词： optimization algorithms dynamic data structures multi-particle system Delaunay tessellation regular subdivision segment tree

来源：评论

学校读者我要写书评

暂无评论

: EXPERIMENTING WITH SKELETONS IN THE SHARED ADDRESS MODEL

引用

Parallel Processing Letters 2003年第3期13卷 449-460页

作者： MARCO ALDINUCCI Inst. of Information Science and Technologies (ISTI) – National Research Council (CNR) Via Moruzzi 1 I–56124 PISA Italy

We discuss the lack of expressivity in some skeleton-based parallel programming frameworks. The problem is further exacerbated when approaching irregular problems and dealing with dynamic data structures. Shared memory programming has been argued to have substantial ease of programming advantages for this class of problems. We present the library which represents an attempt to merge the two programming models by introducing skeletons in a shared memory framework.

关键词： Skeletons dynamic data structures software DSM cluster of workstations

来源：评论

学校读者我要写书评

暂无评论

Optimal solutions for the temporal precedence problem

引用

ALGORITHMICA 2002年第4期33卷 494-510页

作者： Brodal, GS Makris, C Sioutas, S Tsakalidis, A Tsichlas, K Aarhus Univ Dept Comp Sci BRICS DK-8000 Aarhus Denmark Univ Patras Dept COmp Engn & Informat GR-26500 Patras Greece Comp Technol Inst GR-26110 Patras Greece

In this paper we refer to the Temporal Precedence Problem on Pure Pointer Machines. This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations: insert and precedes. The operation insert(a) introduces a new element a in the structure, while the operation precedes(a, b) returns true iff element a was inserted before element b temporally In [11] a solution was provided to the problem with worst-case time complexity O(log log n) per operation and O(n log log n) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Omega(log log n) for the Pure Pointer Machine model of computation. In this paper we present two simple solutions with linear space and worst-case constant insertion time. In addition, we describe two algorithms that can handle the precedes(a, b) operation in O(log log d) time, where d is the temporal distance between the elements a and b.

关键词： algorithms dynamic data structures computational complexity

来源：评论

学校读者我要写书评

暂无评论

Lock-free reference counting

引用

DISTRIBUTED COMPUTING 2002年第4期15卷 255-271页

作者： Detlefs, DL Martin, PA Moir, M Steele, GL Sun Microsyst Labs Burlington MA 01803 USA

Assuming the existence of garbage collection makes it easier to design implementations of dynamic-sized concurrent data structures. However, this assumption limits their applicability. We present a methodology that, for a significant class of data structures, allows designers to first tackle the easier problem of designing a garbage-collection-dependent implementation, and then apply our methodology to achieve a garbage-collection-independent one. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.

关键词： lockfree synchronization reference counting memory management dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Sink insertion for mesh improvement

引用

International Journal of Foundations of Computer Science 2002年第2期13卷 223-242页

作者： Edelsbrunner, Herbert Guoy, Damrong Department of Computer Science Duke University Durham NC 27708 United States Raindrop Geomagic Research Triangle Park NC 27709 United States Center for Simulation of Advanced Rockets Computational Science and Engineering Program University of Illinois at Urbana-Champaign Urbana IL 61801 United States

We propose sink insertion as a new technique to improve the mesh quality of Delaunay triangulations. We compare it with the conventional circumcenter insertion technique under three scheduling regimes: incremental, in blocks, and in parallel. Justification for sink insertion is given in terms of mesh quality, numerical robustness, running time, and ease of parallelization. © 2002 World Scientific Publishing Company.

关键词： Delaunay triangulations dynamic data structures experimentation Mesh generation mesh quality parallel meshing

来源：评论

学校读者我要写书评

暂无评论

Generating test data for functions with pointer inputs 17

Generating test data for functions with pointer inputs

引用

17th IEEE International Conference on Automated Software Engineering (ASE 2002)

作者： Visvanathan, S Gupta, N Univ Arizona Dept Comp Sci Tucson AZ 85721 USA

ISBN: (纸本)0769517366

Generating test inputs for a path in a function with integer and real parameters is an important but difficult problem. The problem becomes more difficult when pointers are passed as inputs to a function. In this case, the shape of the input data structure as well as the data values in the fields of this data structure need to be determined for traversal of the given path. The existing techniques to address this problem are inefficient since they use backtracking to simultaneously satisfy the constraints on the pointer variables and the data values used along the path. In this paper, we develop a novel approach that allows the generation of the shape of an input data structure to be done independently of the generation of its data values so as to force the con trol flow of a function along a given path. We also present a new technique that generates the shape of the input data structure by solving a set of pointer constraints derived in a single pass of the statements along the path. Although simple, our approach is powerful in handling pointer aliasing. It is efficient and provides a practical solution to generating test data for functions with pointer inputs.

关键词： test data generation path testing dynamic data structures iterative relaxation methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：