纳金网

标题: Coherent Parallel Hashing [打印本页]

作者: 晃晃 时间: 2011-12-28 10:30
标题: Coherent Parallel Hashing
Coherent Parallel Hashing

Ismael Garc´ ıa1;2 Sylvain Lefebvre2 Samuel Hornus2 Anass Lasram2

1GGG / Universitat de Girona 2ALICE / INRIA

Abstract

Recent spatial hashing schemes hash millions of keys in parallel,

compacting sparse spatial data in small hash tables while still allow-

ing for fast access from the GPU. Unfortunately, available schemes

suffer from two drawbacks: Multiple***ns of the cons***ction pro-

cess are often required before success, and the random nature of the

hash functions decreases access performance.

We introduce a new parallel hashing scheme which reaches high

load factor with a very low failure rate. In addition our scheme has

the unique advantage to exploit coherence in the data and the access

patterns for faster performance. Compared to existing approaches,

it exhibits much greater locality of memory accesses and consistent

execution paths within groups of threads. This is especially well

suited to Computer Graphics applications, where spatial coherence

is common. In absence of coherence our scheme performs similarly

to previous methods, but does not suffer from cons***ction failures.

Our scheme is based on the Robin Hood scheme modiﬁed to

quickly abort queries of keys that are not in the table, and to pre-

serve coherence. We demonstrate our scheme on a variety of data

sets. We analyze cons***ction and access performance, as well as

cache and threads behavior.

CR Categories: I.3.6 [Computer Graphics]: Methodology and

Techniques—Graphics data s***ctures and data types;

Keywords: spatial, parallel, coherent, hashing, sparse data

1 Introduction

Sparse spatial data is very common in Computer Graphics and ﬁnd-

ing the good tradeoff between access performance and efﬁcient

storage is an ongoing challenge. Spatial hashing has proven use-

ful in these situations, enabling data to be tightly packed while still

allowing fast random access. It has been successfully applied for

texturing, rendering, collision detection and animation.

Using a spatial hash, data is stored in a single array—the hash

table—addressed through a hash function. The hash function com-

putes the data location in the hash table from the query coordinates,

or keys. There have been several developments lately, improving

query and cons***ction times, and in particular enabling fast paral-

lel cons***ction on GPUs.

The ﬁrst spatial hashing schemes focused essentially on reaching

good load factors while having a constant time and simple access

to the data from the GPU. Lefebvre and Hoppe [2006] proposed a

static hash cons***ction enabling access to the data with as little as

two memory accesses and one addition. However, to achieve this

result the hash has to be perfect: All keys corresponding to deﬁned

data should map to different locations in the hash table. In other

words, there are no collisions. Building such a constrained hash

function requires an off–line cons***ction process, limiting this ap-

proach to static cases.

作者: 奇 时间: 2012-1-20 23:28
年末来了，事情也多了！总结一年的经验，续写明年的计划！亲爱的朋友们，要注意身体，要开开心心的工作，健健康康的生活，舒舒服服的过年！

作者: 菜刀吻电线 时间: 2012-2-18 23:25
爱咋咋地！

作者: 菜刀吻电线 时间: 2012-2-20 23:23
我也来支持下

作者: 晃晃 时间: 2012-3-15 23:31
已阵亡的蝶随风舞说过偶尔按一下 CTRL A 会发现世界还有另一面

作者: 晃晃 时间: 2012-3-20 23:27
谢谢楼主，真是太实用了

作者: 菜刀吻电线 时间: 2012-4-10 23:20
其实楼主所说的这些，俺支很少用！

作者: 菜刀吻电线 时间: 2012-4-14 23:21
既来之，则看之！

作者: 奇 时间: 2012-7-27 23:20
“再次路过……”我造一个-----特别路过

作者: tc 时间: 2012-7-27 23:27
谢谢楼主，真是太实用了

欢迎光临纳金网 (http://go.narkii.com/club/)