Version: develop

# 空间稀疏数据结构

## 动机

##### note

• 使用索引访问，和访问稠密数据结构的方式一样。
• 迭代时自动并行。
• 自动内存访问优化。

##### note

Taichi 中的稀疏矩阵通常不是通过空间稀疏数据结构来实现的。 请参阅 稀疏矩阵

## Taichi 中的空间稀疏数据结构

Taichi 中的空间稀疏数据结构由 `pointer``bitmasked``dynamic`，和 `dense` SNode 组成。 一个只由 `dense` SNode 组成的 SNode 树不是空间稀疏数据结构。

### 指针 SNode

pointer.py
``x = ti.field(ti.f32)block = ti.root.pointer(ti.ij, (4,4))pixel = block.dense(ti.ij, (2,2))pixel.place(x)@ti.kerneldef activate():    x[2,3] = 1.0    x[2,4] = 2.0@ti.kerneldef print_active():    for i, j in block:        print("Active block", i, j)    # output: Active block 1 1    #         Active block 1 2    for i, j in x:        print('field x[{}, {}] = {}'.format(i, j, x[i, j]))    # output: field x[2, 2] = 0.000000    #         field x[2, 3] = 1.000000    #         field x[3, 2] = 0.000000    #         field x[3, 3] = 0.000000    #         field x[2, 4] = 2.000000    #         field x[2, 5] = 0.000000    #         field x[3, 4] = 0.000000    #         field x[3, 5] = 0.000000``

### 位掩码 SNode

``x = ti.field(ti.f32)block = ti.root.pointer(ti.ij, (4,4))pixel = block.bitmasked(ti.ij, (2,2))pixel.place(x)@ti.kerneldef activate():    x[2,3] = 1.0    x[2,4] = 2.0@ti.kerneldef print_active():    for i, j in block:        print("Active block", i, j)    for i, j in x:        print('field x[{}, {}] = {}'.format(i, j, x[i, j]))``

### 动态 SNode

Taichi officially supports dynamic data structure Dynamic SNode since version v1.4.0. You can think of a dynamic SNode as a `List` that can only store data of a fixed type. The element types it supports include scalars, vectors/matrices, and structs. It also supports the following three APIs:

1. `append`: Dynamically adds an element, equivalent to the `append` method of a Python list.
2. `deactivate`: Clears all stored elements, equivalent to the `clear` method of a Python list.
3. `length`: Gets the actual number of elements currently stored, equivalent to the `__len__` method of a Python list.

All three methods must be called inside the Taichi scope.

Unfortunately, Dynamic SNode does not support dynamically deleting elements like `pop` and `remove`. This is because it is difficult to implement these operations with high performance in parallel computing.

##### note

Here are a few rules you must obey when using Dynamic Snode:

• Dynamic SNode can only be used in the CPU and CUDA backends.

• A dynamic SNode must have one axis only, and the axis must be the last axis.

• 动态 SNode 下不可再放置其他 SNode。 换言之，动态 SNode 必须直接放置在 field 中。

• 沿着从动态 SNode 到 SNode 树根节点的路径，其他 SNode 不能 具有与动态 SNode 相同的轴。

For example, to declare a one-dimensional dynamic list `x` that stores integers, we can write:

``S = ti.root.dynamic(ti.i, 1024, chunk_size=32)x = ti.field(int)S.place(x)``

Let's explain the meaning of these three lines of code:

1. In the first line of code, `ti.root.dynamic` means that the direct parent node of `S` is `ti.root`. Generally, calling `S = P.dynamic()` for an SNode `P` means the direct parent node of `S` in the Snode tree is `P`. Hence this operation specifies the position of `S` in the SNode tree system.
2. The first parameter of the `dynamic` function is the axis on which `S` is located. This axis must be one-dimensional and cannot have been used by any parent node of `S`. Here we use the axis `ti.i` (equivalent to `axis=0` in NumPy).
3. The second parameter of the dynamic function is the maximum length of `S`. Since Dynamic SNode dynamically allocates memory as needed, it does not occupy space when there is no data. However, this maximum length also has an upper limit (the maximum value of 32-bit int type), so it is not possible to assign an astronomical number to it at will. It is also possible to add elements beyond this maximum length, and elements outside the range can also be accessed normally using subscripts, but we recommend keeping the size of the list within the maximum length range.
4. The third parameter `chunk_size` will be explained later in this article.
5. After obtaining the Dynamic SNode `S` in this way, we declare an integer field variable `x = ti.field(int)`, and then call `S.place(x)` to convert `x` into a data structure described by `S`. Before calling `place`, `x` cannot be used to store data; after calling `place`, `x` can be used as a mutable list of type `int`.

For example, we can use the `append` method to add data to `x`, and call the `length` function to get the actual length of `x`. Both functions must be called inside the kernel:

``@ti.kerneldef add_data():    for i in range(1000):        x.append(i)        print(x.length())add_data()``

We can also call the `deactivate` method of `x` to clear the entire list, which is equivalent to restoring `x` to its uninitialized state:

``@ti.kerneldef clear_data():    x.deactivate()    print(x.length())  # will print 0``

Returning to the explanation of the `chunk_size` parameter: the implementation of Dynamic SNode internally uses linked lists, where multiple elements are densely packed into a node (or "chunk") of the linked list, with each chunk containing `chunk_size` elements. Element allocation and deallocation are performed in units of chunks. The following diagram illustrates how `x` is laid out in memory (with `k = 32`):

Thus, the actual number of chunks allocated is `ceil(x.length() / chunk_size)`.

We can also define more complex variable-length lists. For example, the following code defines an array `x` of length `n = 10`, where each element of `x` is a one-dimensional variable-length list:

``S = ti.root.dense(ti.i, 10).dynamic(ti.j, 1024, chunk_size=32)x = ti.field(int)S.place(x)``

Here, `ti.root.dense(ti.i, 10)` is a Dense SNode that represents a dense array of length 10 along the `ti.i` axis. `S = ti.root.dense(ti.i, 10).dynamic(ti.j, ...)` represents a child node of this Dense SNode, occupying the `ti.j` axis (which is different from the parent node!). The layout of `x` in memory is illustrated in the following diagram:

As with the one-dimensional case, you can dynamically add elements to the i-th list using `x[i].append()`, get the current length of the i-th list using `x[i].length()`, and clear the ith list using `x[i].deactivate()`.

``@ti.kerneldef add_data():    for i in range(10):        for j in range(i):            x[i].append(j)        print(x[i].length())  # will print i    for i in range(10):        x[i].deactivate()        print(x[i].length())  # will print 0``

All of the above discussion applies to using Dynamic SNode with other numeric types. For vector/matrix and struct types, the steps are identical. For example, consider the following code using struct types:

``S = ti.root.dynamic(ti.i, 1024, chunk_size=32)SphereType = ti.types.struct(center=ti.math.vec3, radius=float)x = SphereType.field()S.place(x)``

Here, `x` is a one-dimensional variable-length list that can store values of type `SphereType`.

## 空间稀疏数据结构的计算

### 显式操作和查询稀疏性

Taichi 还提供可以显示操作数据结构稀疏性的 API。 你可以手动检查 SNode 的活跃度，激活 SNode，或者使 SNode 失活。 我们现在基于如下定义的 field 来说明这些功能。

``x = ti.field(dtype=ti.i32)block1 = ti.root.pointer(ti.ij, (3, 3))block2 = block1.pointer(ti.ij, (2, 2))pixel = block2.bitmasked(ti.ij, (2, 2))pixel.place(x)``

#### 1. 活跃度检查

``@ti.kerneldef activity_checking(snode: ti.template(), i: ti.i32, j: ti.i32):    print(ti.is_active(snode, [i, j]))for i in range(3):    for j in range(3):        activity_checking(block1, i, j)for i in range(6):    for j in range(6):        activity_checking(block2, i, j)for i in range(12):    for j in range(12):        activity_checking(pixel, i, j)``

#### 2. 激活

``@ti.kerneldef activate_snodes():    ti.activate(block1, [1, 0])    ti.activate(block2, [3, 1])    ti.activate(pixel, [7, 3])activity_checking(block1, 1, 0) # output: 1activity_checking(block2, 3, 1) # output: 1activity_checking(pixel, 7, 3)  # output: 1``

#### 3. 失活

• 使用 `ti.deactivate(snode, [i, j, ...])` 显式让 `snode[i, j, ...]` 的一个单元转为不活跃。
• 使用 `snode.deactivate_all()` 来取消激活 SNode `snode` 的所有单元。 这个操作也会递归地使其所有的子节点不再活跃。
• 使用 `ti.disactivate_all_snodes()` 来取消激活所有稀疏 SNode 的所有单元。

##### note

• 不会递归取消激活一个单元的所有后代。
• 不会触发取消激活其父容器，即使父容器的所有子容器都已取消激活。

#### 4. 祖先索引查询

``print(ti.rescale_index(x, block1, ti.Vector([7, 3]))) # output: [1, 0]print(ti.rescale_index(x, block2, [7, 3]))            # output: [3, 1]print(ti.rescale_index(x, pixel,  [7, 3]))            # output: [7, 3]print(ti.rescale_index(block2, block1, [3, 1]))       # output: [1, 0]``

## Sparse grid

We now show an example of how to create a sparse grid with our simplified API(`ti.sparse.grid()`), and how to print the usage with `ti.sparse.usage()`.

``import taichi as ti# create a 2D sparse gridgrid = ti.sparse.grid(    {        "pos": ti.math.vec2,        "mass": ti.f32,        "grid2particles": ti.types.vector(20, ti.i32),    },    shape=(10, 10),)# accessgrid[0, 0].pos = ti.math.vec2(1, 2)grid[0, 0].mass = 1.0grid[0, 0].grid2particles[2] = 123# print the usage of the sparse grid, which is in [0,1]ti.sparse.usage(grid)``

possible output:

``Grid usage:  0.010000``

## 扩展阅读

Taichi elements 是一个在 Taichi 稀疏网格上实现的高性能 MLS-MPM 求解器。