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

22nd IEEE Annual International Symposium on Field-Programmable Custom Computing Machines ((FCCM)

作者： Winterstein, Felix Bayliss, Samuel Constantinides, George A. European Space Agcy Ground Stn Syst Div Robert Bosch Str 5 D-64293 Darmstadt Germany Imperial Coll London Dept Elect & Elect Engn London SW7 2AZ England

ISBN: (纸本)9781479951116

The capabilities of modern FPGAs permit the mapping of increasingly complex applications into reconfigurable hardware. High-level synthesis (HLS) promises a significant shortening of the FPGA design cycle by raising the abstraction level of the design entry to high-level languages such as C/C++. Applications using dynamic, pointer-based data structures and dynamic memory allocation, however, remain difficult to implement well, yet such constructs are widely used in software. Automated optimizations that aim to leverage the increased memory bandwidth of FPGAs by distributing the application data over separate banks of on-chip memory are often ineffective in the presence of dynamic data structures, due to the lack of an automated analysis of pointer-based memory accesses. In this work, we take a step towards closing this gap. We present a static analysis for pointer-manipulating programs which automatically splits heap-allocated data structures into disjoint, independent regions. The analysis leverages recent advances in separation logic, a theoretical framework for reasoning about heap-allocated data which has been successfully applied in recent software verification tools. Our algorithm focuses on dynamic data structures accessed in loops and is accompanied by automated source-to-source transformations which enable automatic loop parallelization and memory partitioning by off-the-shelf HLS tools. We demonstrate the successful loop parallelization and memory partitioning by our tool flow using three real-life applications which build, traverse, update and dispose dynamically allocated data structures. Our case studies, comparing the automatically parallelized to the non-parallelized HLS implementations, show an average latency reduction by a factor of 2.5 across our benchmarks.

关键词： FPGA high-level synthesis memory system dynamic data structures separation logic static analysis

来源：评论

学校读者我要写书评

暂无评论

dynamic Ray Stabbing

引用

ACM TRANSACTIONS ON ALGORITHMS 2014年第2期11卷 11-11页

作者： Tao, Yufei Chinese Univ Hong Kong Dept Comp Sci & Engn Sha Tin Hong Kong Peoples R China

We consider maintaining a dynamic set S of N horizontal segments in R-2 such that, given a vertical ray Q in R-2, the segments in S intersecting Q can be reported efficiently. In the external memory model, we give a structure that consumes O(N/B) space, answers a query in O(log(B) N + K/B) time (where K is the number of reported segments), and can be updated in O(log(B) N) amortized time per insertion and deletion. With B set to a constant, the structure also works in internal memory, consuming space O(N), answering a query in O(log N + K) time, and supporting an update in O(log N) amortized time.

关键词： Ray stabbing segment intersection computational geometry dynamic data structures pointer machines

来源：评论

学校读者我要写书评

暂无评论

Verification of complex dynamic data tree with mu-calculus

引用

AUTOMATED SOFTWARE ENGINEERING 2013年第4期20卷 569-612页

作者： del Mar Gallardo, Maria Sanan, David Univ Malaga E-29071 Malaga Spain

The problem of verifying software systems that use dynamic data structures (such as linked lists, queues, or binary trees) has attracted increasing interest over the last decade. dynamic structures are not easily supported by verification techniques because, among other reasons, it is difficult to efficiently manage the pointer-based internal representation. This is a key aspect when, for instance, the goal is to construct a verification tool based on model checking techniques. In addition, since new nodes can be dynamically inserted or extracted from the structure, the shape of the dynamic data (and other more specific properties) may vary at runtime, with errors such as the non desirable sharing between two nodes being difficult to detect. In this paper, we propose to use mu-calculus to describe and analyze with model checking techniques dynamic data structures such as lists and trees. The expressiveness of mu-calculus makes it possible to naturally describe these structures. In addition, following the ideas of separation logic, the logic has been extended with a new operator capable of describing the non-sharing property, which is essential when analyzing dynamic data structures.

关键词： Model checking Mu-calculus dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Space-efficient data-analysis queries on grids

引用

THEORETICAL COMPUTER SCIENCE 2013年 482卷 60-72页

作者： Navarro, Gonzalo Nekrich, Yakov Russo, Luis M. S. Univ Chile Dept Comp Sci Santiago Chile Univ Tecn Lisboa Inst Super Tecn P-1096 Lisbon Portugal

We consider various data-analysis queries on two-dimensional points. We give new space/time tradeoffs over previous work on geometric queries such as dominance and rectangle visibility, and on semigroup and group queries such as sum, average, variance, minimum and maximum. We also introduce new solutions to queries less frequently considered in the literature such as two-dimensional quantiles, majorities, successor/predecessor, mode, and various top-k queries, considering static and dynamic scenarios. (C) 2012 Elsevier S.V. All rights reserved.

关键词： Range queries databases Succinct data structures dynamic data structures Statistical database queries Orthogonal range queries Point dominance Rectangle visibility Wavelet tree Range minimum queries Alpha majority Quantile Top-k Mode

来源：评论

学校读者我要写书评

暂无评论

The linked list representation of n LIFO-stacks and/or FIFO-queues in the single-level memory

引用

INFORMATION PROCESSING LETTERS 2013年第19-21期113卷 832-835页

作者： Sokolov, A. V. Drac, A. V. IAMR KarSC RAS Petrozavodsk Russia

In many applications there is a problem of representation of multiple LIFO-stacks and/or FIFO-queues in the single-level memory. This paper concerns issues related to building mathematical model of process of working with them in the case of linked list representation. This model was constructed as n-dimensional random walk on the integer lattice in some regions of n-dimensional space. (c) 2013 Elsevier B.V. All rights reserved.

关键词： data structures Linked lists FIFO-stacks LIFO-queues dynamic data structures Mathematical modeling

来源：评论

学校读者我要写书评

暂无评论

Exploration methodology of dynamic data structures in multimedia and network applications for embedded platforms

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2008年第11期54卷 1030-1038页

作者： Papadopoulos, Lazaros Baloukas, Christos Soudris, Dimitrios Democritus Univ Thrace VLSI Design & Testing Ctr Dept Elect & Comp Engn GR-67100 Xanthi Greece

In the last years, there is a trend towards network and multimedia applications to be implemented in portable devices. These applications usually contain complex dynamic data structures. The appropriate selection of the dynamic data type (DDT) combination of an application affects the performance and the energy consumption of the whole system. Thus, DDT exploration methodology is used to perform trade-offs between design factors, such as performance and energy consumption. In this paper we provide a new approach to the DDT exploration procedure, based on a new library of DDTs which remedies the limitations of an existing solution and allows the DDT optimization of a wider range of application domains. Using the new library, we performed DDT exploration in network and multimedia benchmarks and achieved performance and energy consumption improvements up to 22% and 5.8%, respectively. (C) 2008 Elsevier B.V. All rights reserved.

关键词： dynamic data structures Embedded systems Low energy consumption

来源：评论

学校读者我要写书评

暂无评论

EXTERNAL MEMORY ORTHOGONAL RANGE REPORTING WITH FAST UPDATES

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2013年第2期23卷 141-157页

作者： Nekrich, Yakov Univ Kansas Dept Elect Engn & Comp Sci Lawrence KS 66045 USA

In this paper we describe data structures for orthogonal range reporting in external memory that support fast update operations. The query costs either match the query costs of the best previously known data structure... 详细信息

关键词： External memory model dynamic data structures orthogona lrange reporting

来源：评论

学校读者我要写书评

暂无评论

MULTIPLE-SOURCE SHORTEST PATHS IN EMBEDDED GRAPHS

引用

SIAM JOURNAL ON COMPUTING 2013年第4期42卷 1542-1571页

作者： Cabello, Sergio Chambers, Erin W. Erickson, Jeff Univ Ljubljana IMFM Dept Math Ljubljana 61000 Slovenia Univ Ljubljana FMF Dept Math Ljubljana 61000 Slovenia St Louis Univ Dept Math & Comp Sci St Louis MO 63103 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA

Let G be a directed graph with n vertices and nonnegative weights in its directed edges, embedded on a surface of genus g, and let f be an arbitrary face of G. We describe a randomized algorithm to preprocess the graph in O(gn log n) time with high probability, so that the shortest-path distance from any vertex on the boundary of f to any other vertex in G can be retrieved in O(log n) time. Our result directly generalizes the O(n log n)-time algorithm of Klein [ Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of f. As an application of our algorithm, we describe algorithms to compute a shortest noncontractible or nonseparating cycle in embedded, undirected graphs in O(g(2)n log n) time with high probability. Our high-probability time bounds hold in the worst case for generic edge weights or with an additional O(log n) factor for arbitrary edge weights.

关键词： computational topology topological graph theory parametric shortest paths dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Nowhere-dense classes of graphs

Nowhere-dense classes of graphs

引用

作者： Tůma, Vojtěch Charles University of Prague

In this thesis we study sparse classes of graphs and their properties usable for design of algorithms and data structures. Our specific focus is on the con- cepts of bounded expansion and tree-depth, developed in recent years mainly by J. Nešetřil and P. Ossona de Mendez. We first give a brief introduction to the theory as whole and survey tools and results from related areas of parametrised complexity and algorithmic model theory. The main part of the thesis, application of the theory, presents two new dynamic data structures. The first is for keeping a tree-depth decomposition of a graph, the second counts appearances of fixed subgraphs in a given graph. The time and space complexity of operations of both structures is guaranteed to be low when used for sparse graphs. 1

关键词： sparse graph theory algorithmic metatheorems dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

AN OPTIMAL dynamic data STRUCTURE FOR STABBING-SEMIGROUP QUERIES

引用

SIAM JOURNAL ON COMPUTING 2012年第1期41卷 104-127页

作者： Agarwal, Pankaj K. Arge, Lars Kaplan, Haim Molad, Eyal Tarjan, Robert E. Yi, Ke Duke Univ Dept Comp Sci Durham NC 27708 USA Aarhus Univ Dept Comp Sci Ctr Mass Data Algorithm MADALGO DK-8000 Aarhus Denmark Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Hewlett Packard Corp Palo Alto CA 94304 USA HKUST Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

Let S be a set of n intervals in R, and let (S, +) be any commutative semigroup. We assign a weight omega(s) is an element of S to each interval in S. For a point x is an element of R, let S(x) subset of S be the set of intervals that contain x. Given a point q is an element of R, the stabbing-semigroup query asks for computing Sigma(s is an element of S(q)) omega(s). We propose a linear-size dynamic data structure, under the pointer-machine model, that answers queries in worst-case O(log n) time and supports both insertions and deletions of intervals in amortized O(log n) time. It is the first data structure that attains the optimal O(log n) bound for all three operations. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in O(logB n) I/Os, where B is the disk block size. For the restricted case of a nested family of intervals (either every pair of intervals is disjoint or one contains the other), we present a simpler solution based on dynamic trees.

关键词： dynamic data structures stabbing queries semigroup queries

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：