การเข้ารหัส Tensor บางส่วนเป็นแอตทริบิวต์ในการเข้ารหัสข้อมูล เกี่ยวกับทรัพย์สินที่หาไม่ได้จาก Tensor และได้รับแรงบันดาลใจ โดย TACO อย่างเป็นทางการของ Tensors ที่กระจัดกระจาย การเข้ารหัสนี้จะถูกนำมาใช้ในท้ายที่สุด ผ่านเครื่องมือแยกวิเคราะห์เพื่อสร้างโค้ดบางส่วนโดยอัตโนมัติจาก การนำไปใช้คำนวณโดยอิสระโดยไม่ต้องพึ่งพิการ กล่าวคือ การกระจัดกระจายโดยนัย การนำเสนอแบบกว้างๆ จะแสดงเป็นการนำเสนอแบบ "เล็กน้อยเกินไป" ลูปแบบทำซ้ำร่วมกันทำงานในพื้นที่เก็บข้อมูลน้อย มากกว่า Tensor กับจำนวนส่วนน้อย การเข้ารหัส ต้องคำนึงถึงบัตรคอมไพเลอร์ที่ทำงานก่อนบัตรสปาร์เซอร์นี้ ของความหมายของประเภท Tensor ที่มีการเข้ารหัสเพียงเล็กน้อย
ในการเข้ารหัสนี้ เราจะใช้มิติข้อมูลเพื่อ หมายถึงแกนของ Tensor ความหมาย และระดับ เพื่ออ้างถึงแกนของรูปแบบพื้นที่เก็บข้อมูลจริง ซึ่งก็คือค่า การแสดงการทำงานของ Tensor ที่กระจัดกระจายในหน่วยความจำ จำนวน มิติข้อมูลปกติจะเท่ากับ จำนวนระดับ (เช่น รูปแบบพื้นที่เก็บข้อมูล CSR) อย่างไรก็ตาม การเข้ารหัสยังแมป มิติข้อมูลให้มีลำดับสูงกว่า (เช่น เพื่อเข้ารหัสรูปแบบพื้นที่เก็บข้อมูล BSR แบบบล็อกบางส่วน) หรือในระดับที่ต่ำกว่า (เช่น เพื่อทำให้มิติข้อมูลเป็นเส้นตรงเป็นระดับเดียวในพื้นที่เก็บข้อมูล)
การเข้ารหัสประกอบด้วยแผนที่ที่ให้ข้อมูลต่อไปนี้
- ข้อกำหนดเกี่ยวกับมิติข้อมูลตามลำดับตามลำดับ โดยแต่ละรายการจะกำหนดสิ่งต่อไปนี้
- ขนาดมิติข้อมูล (โดยนัยจากรูปร่างมิติข้อมูลของ Tensor)
- นิพจน์มิติข้อมูล
- ข้อกำหนดระดับตามลำดับ ซึ่งมีข้อกำหนดที่
level-type ซึ่งจะกําหนดวิธีจัดเก็บระดับ ประเภทแต่ละระดับ
ประกอบด้วย
- นิพจน์ระดับ ซึ่งจะกำหนดสิ่งที่เก็บไว้
- level-Format
- คอลเล็กชันของพร็อพเพอร์ตี้ระดับที่ใช้กับรูปแบบระดับ
แต่ละระดับเป็นนิพจน์แบบสัมพันธ์ ตัวแปรมิติข้อมูล ดังนั้น ระดับของนิพจน์จะรวมกันเป็นนิยาม แผนที่เสริมจากพิกัดมิติไปยัง พิกัดระดับ นิพจน์มิติข้อมูล ระบุแผนที่ผกผัน ซึ่งต้องระบุสำหรับกรณีที่ซับซ้อนซึ่งไม่สามารถอนุมานได้ โดยอัตโนมัติ
มิติข้อมูลแต่ละรายการอาจมี SparseTensorDimSliceAttr หรือไม่ก็ได้
ภายในรูปแบบพื้นที่เก็บข้อมูลที่กระจัดกระจาย เราหมายถึงดัชนีที่เก็บไว้อย่างชัดแจ้ง
เป็นพิกัดและออฟเซ็ตลงในรูปแบบพื้นที่เก็บข้อมูลเป็นตำแหน่ง
รูปแบบระดับที่รองรับมีดังต่อไปนี้
- dense : รายการทั้งหมดในระดับนี้จะเก็บอยู่
- บีบอัด : จัดเก็บเฉพาะรายการที่ไม่ใช่หน่วยเซอร์วิสในระดับนี้
- loose_compressed : ในรูปแบบที่บีบอัด แต่สามารถเพิ่มพื้นที่ว่างระหว่างภูมิภาค
- singleton : รูปแบบหนึ่งของรูปแบบที่บีบอัด ซึ่งไม่มีพิกัดพี่น้อง
- block2_4 : การบีบอัดใช้การเข้ารหัส 2:4 ต่อบล็อก 1x4
สำหรับระดับที่บีบอัด แต่ละช่วงตำแหน่งจะแสดงเป็นแบบกะทัดรัด
ด้วย pos(i) ต่ำสุดและ pos(i+1) - 1 สูงสุด ซึ่งมีความหมายว่า
ช่วงที่ต่อเนื่องกันจะต้องปรากฏตามลำดับโดยไม่มี "ช่องว่าง" อยู่ระหว่าง
ให้พวกเขา รูปแบบที่บีบอัดแบบหลวมๆ จะช่วยคลายข้อจำกัดเหล่านี้ด้วยการแสดงแต่ละ
ช่วงตำแหน่งที่มี lo(i) ระดับล่างและ hi(i) ระดับบน ซึ่ง
อนุญาตให้ช่วงเวลาปรากฏตามลำดับที่กำหนดเองและมีระยะห่างระหว่างช่องศอก
โดยค่าเริ่มต้น ประเภทของระดับแต่ละระดับจะมีคุณสมบัติไม่ซ้ำกัน (ไม่ซ้ำกัน พิกัดที่ระดับนั้น) และเรียงลำดับ (พิกัดจะจัดเรียงที่ ระดับ) สามารถเพิ่มพร็อพเพอร์ตี้ต่อไปนี้ในรูปแบบระดับเพื่อเปลี่ยนแปลง การทำงานเริ่มต้นนี้:
- ไม่ซ้ำกัน : พิกัดที่ซ้ำกันอาจปรากฏที่ระดับ
- nonordered : พิกัดอาจปรากฏตามลำดับของอาร์กิวเมนต์
นอกจากแผนที่แล้ว ยังมีฟิลด์ที่ไม่บังคับ 2 ฟิลด์ต่อไปนี้ด้วย
บิตความกว้างที่ต้องใช้สำหรับการจัดเก็บตำแหน่ง (ออฟเซ็ตปริพันธ์ เป็นรูปแบบพื้นที่เก็บข้อมูลที่กระจัดกระจาย) ความกว้างที่แคบทำให้หน่วยความจำลดลง ฟุตพริ้นท์จากการจัดเก็บข้อมูลด้านเหนือศีรษะ ตราบใดที่ความกว้างพอจะเพียงพอ กำหนดช่วงทั้งหมดที่ต้องการ (เช่น จำนวนสูงสุดของที่จัดเก็บ รายการในทุกระดับทางอ้อม) ตัวเลือกได้แก่
8,1632,64หรือค่าเริ่มต้น0เพื่อบ่งบอกบิตความกว้างแบบดั้งเดิมบิตความกว้างที่ต้องใช้ในการจัดเก็บข้อมูลพิกัด (พิกัด ของรายการที่จัดเก็บไว้) ความกว้างที่แคบจะลดพื้นที่หน่วยความจำ ของพื้นที่เก็บข้อมูลเหนือศีรษะ ตราบใดที่ความกว้างเพียงพอสำหรับการกำหนด ช่วงทั้งหมดที่ต้องการ (เช่น ค่าสูงสุดของแต่ละ Tensor ประสานงานในทุกระดับ) ตัวเลือกได้แก่
8,16,3264หรือค่าเริ่มต้น0เพื่อบ่งบอกบิตความกว้างแบบดั้งเดิม
ตัวอย่าง
ในรูปแบบ CSR(Compressed Sparse Row)
แสดงด้านล่างของการเข้ารหัส Tensor แบบบาง
จะเป็น:
#CSR = #sparse_tensor.encoding<{
map = (i, j) -> (i : dense, j : compressed)
}>
ซึ่งระบุว่า first dimension (แถว) แมปกับ first level
ซึ่งเป็นระดับ dense ซึ่งระบุด้วยขนาด 4 และ second dimension
(คอลัมน์) จะจับคู่กับ second level ซึ่งระบุด้วยอาร์เรย์ตำแหน่งและ
อาร์เรย์พิกัด ค่า 3 ([1, 1] ในเมทริกซ์ต้นฉบับ) คือ
แสดงด้วยค่าออฟเซ็ตจากอาร์เรย์ตำแหน่ง (หมายเลขแถวของ 3)
1 ในเมทริกซ์ดั้งเดิม เนื่องจากเป็นคู่ออฟเซ็ตที่สองและ
หมายเลขคอลัมน์อยู่ในดัชนี [2 : 4) ในอาร์เรย์พิกัด) และใน
อาร์เรย์พิกัด เราจะเห็นว่าค่าหมายเลขคอลัมน์ของ 3 คือ 1 ใน
เมทริกซ์ต้นฉบับ
สำหรับรูปแบบ BSR(Block Sparse Row) ประเภท Tensor แบบคร่าวๆ คือ
#BSR = #sparse_tensor.encoding<{
map = (i, j) ->
( i floordiv 2 : dense
, j floordiv 2 : compressed
, i mod 2 : dense
, j mod 2 : dense
)
ลองพิจารณาเมทริกซ์แบบกระจัดกระจายต่อไปนี้ซึ่งมีบล็อกขนาด 2x2
Example 2x2 block storage:
+-----+-----+-----+ +-----+-----+-----+
| 1 2 | . . | 4 . | | 1 2 | | 4 0 |
| . 3 | . . | . 5 | | 0 3 | | 0 5 |
+-----+-----+-----+ => +-----+-----+-----+
| . . | 6 7 | . . | | | 6 7 | |
| . . | 8 . | . . | | | 8 0 | |
+-----+-----+-----+ +-----+-----+-----+
ซึ่งท้ายที่สุดแล้วจะจัดเก็บไว้ในรูปแบบ TACO โดยใช้รูปแบบ
Stored as:
positions[1] : 0 2 3
coordinates[1] : 0 2 1
values : 1.000000 2.000000 0.000000 3.000000
4.000000 0.000000 0.000000 5.000000
6.000000 7.000000 8.000000 0.000000
ซึ่งจริงๆ แล้ว รูปแบบการบล็อก NVidia ที่แสดงในเอกสาร cuSparse
บล็อกแถวที่มีขอบเขตแคบ (ม.ป.ป.) Nvidia https://docs.nvidia.com/cuda/cusparse/_images/bsr.png
เรายังรองรับ Nvidia's 2:4 structured sparsity ด้วย
ประเภท Tensor แบบคร่าวๆ มีดังนี้
#NV_24 = #sparse_tensor.encoding<{
map = ( i, j ) -> ( i : dense,
j floordiv 4 : dense,
j mod 4 : block2_4),
crdWidth = 2 // 2-bits for each coordinate
}>
จากเมทริกซ์ตัวอย่างที่ให้ไว้ในเอกสาร NVidia
ตัวอย่างพื้นที่เก็บข้อมูล MMA แบบแยกวิเคราะห์ (ม.ป.ป.). Nvidia https://docs.nvidia.com/cuda/parallel-thread-execution/index.html#warp-level-matrix-instructions-for-sparse-mma
MLIR จะแมปเมทริกซ์นี้กับเลย์เอาต์ที่เหมือนกัน
coordinates[2] :
0 2 0 2 0 2 0 2
1 3 1 3 1 3 1 3
0 1 2 3 0 1 2 3
2 3 0 1 2 3 0 1
0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1
2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3
0 2 0 2 0 2 0 2
1 3 1 3 1 3 1 3
0 1 2 3 0 1 2 3
2 3 0 1 2 3 0 1
0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1
2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3
values :
1.000000 2.000000 3.000000 4.000000 1.000000 2.000000 3.000000 4.000000
5.000000 6.000000 7.000000 8.000000 5.000000 6.000000 7.000000 8.000000
9.000000 10.000000 11.000000 12.000000 9.000000 10.000000 11.000000 12.000000
13.000000 14.000000 15.000000 16.000000 13.000000 14.000000 15.000000 16.000000
17.000000 18.000000 19.000000 20.000000 17.000000 18.000000 19.000000 20.000000
21.000000 22.000000 23.000000 24.000000 21.000000 22.000000 23.000000 24.000000
25.000000 26.000000 27.000000 28.000000 25.000000 26.000000 27.000000 28.000000
29.000000 30.000000 31.000000 32.000000 29.000000 30.000000 31.000000 32.000000
1.000000 2.000000 3.000000 4.000000 1.000000 2.000000 3.000000 4.000000
5.000000 6.000000 7.000000 8.000000 5.000000 6.000000 7.000000 8.000000
9.000000 10.000000 11.000000 12.000000 9.000000 10.000000 11.000000 12.000000
13.000000 14.000000 15.000000 16.000000 13.000000 14.000000 15.000000 16.000000
17.000000 18.000000 19.000000 20.000000 17.000000 18.000000 19.000000 20.000000
21.000000 22.000000 23.000000 24.000000 21.000000 22.000000 23.000000 24.000000
25.000000 26.000000 27.000000 28.000000 25.000000 26.000000 27.000000 28.000000
29.000000 30.000000 31.000000 32.000000 29.000000 30.000000 31.000000 32.000000
ตัวอย่างเพิ่มเติม
// Sparse vector.
#SparseVector = #sparse_tensor.encoding<{
map = (i) -> (i : compressed)
}>
... tensor<?xf32, #SparseVector> ...
// Sorted coordinate scheme.
#SortedCOO = #sparse_tensor.encoding<{
map = (i, j) -> (i : compressed(nonunique), j : singleton)
}>
... tensor<?x?xf64, #SortedCOO> ...
// Batched sorted coordinate scheme, with high encoding.
#BCOO = #sparse_tensor.encoding<{
map = (i, j, k) -> (i : dense, j : compressed(nonunique, high), k : singleton)
}>
... tensor<10x10xf32, #BCOO> ...
// Compressed sparse row.
#CSR = #sparse_tensor.encoding<{
map = (i, j) -> (i : dense, j : compressed)
}>
... tensor<100x100xbf16, #CSR> ...
// Doubly compressed sparse column storage with specific bitwidths.
#DCSC = #sparse_tensor.encoding<{
map = (i, j) -> (j : compressed, i : compressed),
posWidth = 32,
crdWidth = 8
}>
... tensor<8x8xf64, #DCSC> ...
// Block sparse row storage (2x3 blocks).
#BSR = #sparse_tensor.encoding<{
map = ( i, j ) ->
( i floordiv 2 : dense,
j floordiv 3 : compressed,
i mod 2 : dense,
j mod 3 : dense
)
}>
... tensor<20x30xf32, #BSR> ...
// Same block sparse row storage (2x3 blocks) but this time
// also with a redundant reverse mapping, which can be inferred.
#BSR_explicit = #sparse_tensor.encoding<{
map = { ib, jb, ii, jj }
( i = ib * 2 + ii,
j = jb * 3 + jj) ->
( ib = i floordiv 2 : dense,
jb = j floordiv 3 : compressed,
ii = i mod 2 : dense,
jj = j mod 3 : dense)
}>
... tensor<20x30xf32, #BSR_explicit> ...
// ELL format.
// In the simple format for matrix, one array stores values and another
// array stores column indices. The arrays have the same number of rows
// as the original matrix, but only have as many columns as
// the maximum number of nonzeros on a row of the original matrix.
// There are many variants for ELL such as jagged diagonal scheme.
// To implement ELL, map provides a notion of "counting a
// dimension", where every stored element with the same coordinate
// is mapped to a new slice. For instance, ELL storage of a 2-d
// tensor can be defined with the mapping (i, j) -> (#i, i, j)
// using the notation of [Chou20]. Lacking the # symbol in MLIR's
// affine mapping, we use a free symbol c to define such counting,
// together with a constant that denotes the number of resulting
// slices. For example, the mapping [c](i, j) -> (c * 3 * i, i, j)
// with the level-types ["dense", "dense", "compressed"] denotes ELL
// storage with three jagged diagonals that count the dimension i.
#ELL = #sparse_tensor.encoding<{
map = [c](i, j) -> (c * 3 * i : dense, i : dense, j : compressed)
}>
... tensor<?x?xf64, #ELL> ...
// CSR slice (offset = 0, size = 4, stride = 1 on the first dimension;
// offset = 0, size = 8, and a dynamic stride on the second dimension).
#CSR_SLICE = #sparse_tensor.encoding<{
map = (i : #sparse_tensor<slice(0, 4, 1)>,
j : #sparse_tensor<slice(0, 8, ?)>) ->
(i : dense, j : compressed)
}>
... tensor<?x?xf64, #CSR_SLICE> ...