MLIR में स्पार्स टेन्सर के टाइप

स्पार्स टेंसर एन्कोडिंग, जानकारी को कोड में बदलने के लिए एक एट्रिब्यूट है टेंसर के विरल गुणों पर इसके बाद, टीएसीओ ने स्पेयर टेंसर को औपचारिक रूप से व्यवस्थित किया. कोड में बदलने का यह तरीका बाद में इस्तेमाल किया जाता है एक स्पार्सिफ़ायर पास की मदद से, कंप्यूटेशन का स्पार्सिटी-एग्नॉस्टिक निरूपण, उदाहरण के लिए, इंप्लिसिट स्पैर्स निरूपण को एक विशिष्ट विरल निरूपण में बदल दिया जाता है जहां को-इटिंग लूप, स्पार्स स्टोरेज पर काम करते हैं विरलता वाले टेंसर के बजाय फ़ॉर्मैट में एन्कोडिंग इस स्पासिफ़ायर पास से पहले चलने वाले कंपाइलर पास की जानकारी होना ज़रूरी है के सिमैंटिक का इस्तेमाल किया जा सकता है.

इस एन्कोडिंग में, हम डाइमेंशन का इस्तेमाल करके सिमैंटिक टेंसर के ऐक्सिस देखें, और लेवल का इस्तेमाल असल स्टोरेज फ़ॉर्मैट के ऐक्सिस को दिखाने के लिए किया जाता है, जैसे कि मेमोरी में मौजूद स्पैर्स टेंसर का ऑपरेशनल प्रज़ेंटेशन. इतने लोगों को डाइमेंशन आम तौर पर इसके समान होते हैं स्तरों की संख्या (जैसे सीएसआर मेमोरी प्रारूप). हालाँकि, एन्कोडिंग भी मैप कर सकती है हाई-ऑर्डर लेवल के लिए डाइमेंशन (उदाहरण के लिए, ताकि ब्लॉक-स्पार्स BSR स्टोरेज फ़ॉर्मैट को कोड में बदला जा सके) या निचले ऑर्डर के लेवल को कोड में बदला जा सकता है उदाहरण के लिए, स्टोरेज में डाइमेंशन को एक लेवल के तौर पर लीनियर बनाने के लिए.

एन्कोडिंग में एक मैप होता है, जो ये जानकारी देता है:

  • डाइमेंशन स्पेसिफ़िकेशन का ऑर्डर किया गया क्रम, जिसमें से हर जानकारी इनके बारे में बताती है:
    • डाइमेंशन का साइज़ (टेंसर के डाइमेंशन-साइज़ से इंप्लिसिट)
    • डाइमेंशन-एक्सप्रेशन
  • लेवल की खास जानकारी का ऑर्डर वाला क्रम, जिसमें हर एक ज़रूरी जानकारी शामिल होती है level-type दिया गया है, जो बताता है कि लेवल को कैसे सेव किया जाना चाहिए. हर लेवल का टाइप इसमें शामिल है:
    • level-expression, जिससे यह तय होता है कि कौनसा डेटा सेव किया जाएगा
    • लेवल-फ़ॉर्मैट
    • लेवल के फ़ॉर्मैट पर लागू होने वाली लेवल-प्रॉपर्टी का कलेक्शन

हर लेवल-एक्सप्रेशन एक अफ़िनिटी एक्सप्रेशन है के मुकाबले एक से ज़्यादा डाइमेंशन वैरिएबल चुनने की सुविधा मिलती है. इसलिए, लेवल-एक्सप्रेशन को मिलाकर एक आयाम-निर्देशांकों से लेकर लेवल-कोऑर्डिनेट होते हैं. डाइमेंशन-एक्सप्रेशन सामूहिक रूप से इनवर्स मैप की परिभाषा तय करते हैं, इसे सिर्फ़ ऐसे मामलों में दिया जाना चाहिए जहां इसका अनुमान न लगाया जा सके स्वचालित रूप से.

हर डाइमेंशन में एक वैकल्पिक SparseTensorDimSliceAttr भी हो सकता है. स्पार्स स्टोरेज फ़ॉर्मैट में, हम उन इंडेक्स को कहते हैं जो साफ़ तौर पर स्टोर किए जाते हैं निर्देशांक के रूप में और स्थिति के रूप में मेमोरी फ़ॉर्मैट में ऑफ़सेट करते हैं.

इस्तेमाल किए जा सकने वाले लेवल के फ़ॉर्मैट इस तरह हैं:

  • dense : इस लेवल की सभी एंट्री स्टोर की जाती हैं
  • कंप्रेस की गई : इस लेवल पर सिर्फ़ नॉन-ज़ीरो को सेव किया जाता है
  • loose_compressed : जैसे कि कंप्रेस किया गया, लेकिन क्षेत्रों के बीच खाली जगह की मंज़ूरी देता है
  • सिंगलटन : कंप्रेस किए गए फ़ॉर्मैट का एक वैरिएंट, जिसमें निर्देशांक के कोई सिबलिंग नहीं होते हैं
  • block2_4 : कंप्रेशन, हर 1x4 ब्लॉक के लिए 2:4 एन्कोडिंग का इस्तेमाल करता है

कंप्रेस किए गए लेवल के लिए, हर पोज़िशन इंटरवल को कॉम्पैक्ट (कॉम्पैक्ट) में दिखाया जाता है लोअरबाउंड pos(i) और अपरबाउंड pos(i+1) - 1 के साथ रास्ता, जिसका मतलब है कि एक के बाद एक इंटरवल, बिना किसी "होल" के क्रम में दिखना चाहिए बीच में उन्हें. ढीला कंप्रेस किया गया फ़ॉर्मैट हर एक को लोअरबाउंड lo(i) और अपरबाउंड hi(i) के साथ पोज़िशन इंटरवल, जो इंटरवल को मनचाहे क्रम में और उनके बीच कोहनी के कमरे में दिखाने की अनुमति देता है.

डिफ़ॉल्ट रूप से, हर लेवल-टाइप में यूनीक होने की प्रॉपर्टी होती है (कोई डुप्लीकेट नहीं होता) उस स्तर पर निर्देशांक और क्रमित (निर्देशांक उस स्तर पर क्रमबद्ध होते हैं) लेवल). लेवल के फ़ॉर्मैट में बदलाव करने के लिए, इन प्रॉपर्टी को जोड़ा जा सकता है यह डिफ़ॉल्ट व्यवहार:

  • non Unique : लेवल पर डुप्लीकेट निर्देशांक दिख सकते हैं
  • बिना क्रम वाला : निर्देशांक, आर्ब्रिब्रेट्री के क्रम में दिख सकते हैं

मैप के अलावा, ये दो फ़ील्ड वैकल्पिक हैं:

  • स्थिति मेमोरी के लिए ज़रूरी बिट चौड़ाई (इंटिग्रल ऑफ़सेट स्पार्स स्टोरेज स्कीम में भी शामिल किया जाता है. कम चौड़ाई होने से मेमोरी कम हो जाती है ओवरहेड स्टोरेज का इस्तेमाल तब तक किया जा सकता है, जब तक कि चौड़ाई इतनी ज़्यादा हो कि कुल आवश्यक श्रेणी परिभाषित करें (यानी स्टोर की गई अधिकतम एंट्री के लिए उपलब्ध है). आपके पास 8, 16, नेटिव बिटविथ दिखाने के लिए 32, 64 या डिफ़ॉल्ट रूप से 0.

  • निर्देशांक मेमोरी के लिए ज़रूरी बिट चौड़ाई (निर्देशांक) सेव की गई एंट्री) कम चौड़ाई होने से मेमोरी फ़ुटप्रिंट कम हो जाता है का इस्तेमाल किया जा सकता है. कुल ज़रूरी रेंज (जैसे, हर टेंसर की ज़्यादा से ज़्यादा वैल्यू) निर्देशांक शामिल होते हैं. विकल्प हैं: 8, 16, 32, नेटिव बिटविथ दिखाने के लिए 64 या डिफ़ॉल्ट 0.

उदाहरण

CSR(Compressed Sparse Row) फ़ॉर्मैट में नीचे दिखाया गया है, स्पार्स टेंसर एन्कोडिंग होगा:

#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) फ़ॉर्मैट के लिए, स्पार्स टेंसर का टाइप इस तरह है:

#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 |     |
 +-----+-----+-----+    +-----+-----+-----+

जिसे आखिर में टीएसीओ-फ़्लेवर वाले फ़ॉर्मैट में इस तरह सेव किया जाता है

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 दस्तावेज़ में दिया गया है.

स्पैर्स लाइन को ब्लॉक करें. (पेज पब्लिश होने की तारीख पता नहीं है). एनवीडिया. https://docs.nvidia.com/cuda/cusparse/_images/bsr.png

Nvidia's 2:4 structured sparsity का भी इस्तेमाल किया जा सकता है.

इसके लिए स्पार्स टेंसर का टाइप इस तरह है:

#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 के दस्तावेज़ में दिए गए सैंपल मैट्रिक्स को देखते हुए:

स्पार्स एमएमए स्टोरेज का उदाहरण. (n.d.). एनवीडिया. 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> ...