Val 0
Key 0
DATA (N-2 entries)
Val 1
Key 1
Upper
32-bits
Lower
32-bits
Val N-3
Key N-3
Next Ptr
Max Field
NEXT
Lock Field
LOCK
…
…
Figure 2. Format of a chunk of size N
Data Array
20 25 33 … 33
-∞
5 10 … 10
101 570 … …
∞
-∞
10 25 … 25
-∞
570 … …
∞
…
ctr ptr
1
2
12
Head
Array
570 600 810 …
∞
Next
Lock
Figure 3. A chunked skiplist
these requirements by using array-based skiplist nodes and
allowing threads in a warp to cooperate in the execution of
the skiplist operations.
We tackle the problem of scattered memory accesses by
packing consecutive key-value pairs residing in the same
level into large cache-aligned skiplist nodes called chunks,
shown in Fig. 2. Chunks contain a data array, a sorted array
of key-value pairs, along with a LOCK entry and a NEXT
entry consisting of a pointer to the next chunk and a max
field holding the maximum key in the current chunk. hunks
are designed to be read efficiently in the fewest possible
memory transactions.
GFSL consists of several levels of chunked linked lists,
each containing a subset of the keys in the level below, as
seen in Fig. 3. Each chunk’s data array is sorted in rising
order, with empty entries denoted by a special ∞ value and
grouped at the end of the array. In the upper levels the value
field of each entry in the data array points to a chunk in
the level below, and in the bottom level this field will hold
the data element associated with the corresponding key. A
key-value pair in level i + 1 generally points to a chunk
containing the same key in level i, though it may temporarily
point to a chunk containing smaller values during Inserts and
Deletes. The first chunk in each level contains a −∞ key in
the first entry with a pointer to the first chunk in the level
below, and is accessed via a pointer from the Head Array.
The last chunk in every level contains an ∞ value in both
its next-pointer and max fields. ∞ and −∞ are distinct from
keys in the structure.
Threads are divided into groups called teams, which
cooperate to perform the skiplist operations. Teams can be
defined by the user to be either the size of a warp or smaller.
The number of entries in a chunk is equal to the number
of threads in a team, so that the entire chunk is read in a
single kernel instruction (executed in lockstep by the team).
Each thread in a team simultaneously reads data from the
chunk index corresponding to its place within the team (tId).
For a team of size N the first (N-2) threads, called DATA
threads, access the data array, while the last two access the
NEXT and LOCK values respectively. Each thread performs
computations on the value it read then cooperates with the
rest of its team to decide on the next step in the execution
via intra-warp operations.
Structure traversal is similar in spirit to traversal over a
regular skiplist. A team searching for a key k reads the first
chunk in the highest level. Each DATA thread compares k to
the key read from its entry, while the NEXT thread compares
k to the maximum field. The threads share their results and
decide simultaneously how to continue the traversal: either
a lateral step via the next pointer, or a step down to the next
level via a pointer in some DATA field. The team continues
laterally if the searched key is greater than the maximum
and steps down otherwise via the data-entry containing the
largest key smaller or equal to k. If all keys in the chunk are
greater than k then the team must backtrack to the previous
chunk in the level and step down from there.
Insert and Delete operations are likewise performed by an
entire team in tandem while ensuring the chunks remain both
internally and externally sorted. If an insertion occurs when
there is no free space in the data array a split operation
is performed: A new chunk is allocated and added to
the structure after the overflowed chunk. The data array
is divided equally between both chunks, whilst remaining
sorted. Conversely, if a deletion causes a lower bound on
the number of key-value pairs to be crossed then a merge
operation is performed: the chunk is marked as a zombie and
its values are moved to the next chunk in the level. If the
next chunk is too full this operation may cause it to be split.
Pointers are redirected after both split and merge operations
in order to ensure the upper level pointers remain accurate
and to physically remove a zombie from the structure. All
changes to the contents of the skiplist are performed under
the protection of the chunks’ locks, so at most one team can
change the contents of a chunk at any time.
GFSL contains fewer nodes and levels than the classic
skiplist. A single node in GFSL contains several keys, and
so replaces several separate nodes in the classic version.
Thus more keys can be inserted into a level before it
becomes necessary to add a pointer in the level above.
The teams process more data for every memory transaction
than a single thread does in the original algorithm, enabling
faster traversals over the structure, while also causing less
divergence within a warp.
Unlike the classic skiplist algorithm, GFSL does not
predetermine a level for every key inserted. Instead, a key
can be raised to level i + 1 only as a result of a split, i.e.
when a new chunk is added to level i. Raising the key as a
result of insertion of new chunks and not single keys causes
the factor between levels to be tied to the number of entries
in a chunk, aiding in shorter traversals. In an ideal structure
剩余13页未读，继续阅读
weixin_38708841
- 粉丝: 3
- 资源: 945
我的内容管理
展开
最新资源
- C++多态实现机制详解：虚函数与早期绑定
- Java多线程与异常处理详解
- 校园导游系统：无向图实现最短路径探索
- SQL2005彻底删除指南：避免重装失败
- GTD时间管理法：提升效率与组织生活的关键
- Python进制转换全攻略：从10进制到16进制
- 商丘物流业区位优势探究：发展战略与机遇
- C语言实训：简单计算器程序设计
- Oracle SQL命令大全：用户管理、权限操作与查询
- Struts2配置详解与示例
- C#编程规范与最佳实践
- C语言面试常见问题解析
- 超声波测距技术详解：电路与程序设计
- 反激开关电源设计：UC3844与TL431优化稳压
- Cisco路由器配置全攻略
- SQLServer 2005 CTE递归教程：创建员工层级结构
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
