ইনডেক্সিং বিশ্লেষণ

এই নথিটি HLO সূচী বিশ্লেষণের বর্ণনা করে, যা আপনাকে HLO অপ্সের জন্য প্রতীকীভাবে সূচীকরণ মানচিত্র গণনা করতে দেয়। ইন্ডেক্সিং ম্যাপ হল এমন একটি ফাংশন যা একটি টেনসরের সূচককে অন্যটির সূচকে ম্যাপ করে, যেমন একটি এইচএলও নির্দেশনা আউটপুটের সূচকগুলিকে এইচএলও নির্দেশনা ইনপুটগুলির সূচকে বা এর বিপরীতে।

উদাহরণ

tensor<20xf32> থেকে tensor<10x20x30xf32> সম্প্রচারের জন্য

p0 = f32[20] parameter(0)
bc0 = f32[10, 20, 30] broadcast(p0), dimensions={1}

আউটপুট থেকে ইনপুট পর্যন্ত ইন্ডেক্সিং ম্যাপ হল (i, j, k) -> (j) i in [0, 10] , j in [0, 20] এবং k in [0, 30] ।

প্রেরণা

XLA GPU সমন্বিতকরণ, অপারেন্ড ইউটিলাইজেশন, এবং টাইলিং স্কিম (নীচে আরও বিশদ বিবরণ) সম্পর্কে যুক্তির জন্য বেশ কয়েকটি বেসপোক সমাধান ব্যবহার করে। ইন্ডেক্সিং বিশ্লেষণের লক্ষ্য হল এই ধরনের ব্যবহারের ক্ষেত্রে একটি পুনঃব্যবহারযোগ্য উপাদান প্রদান করা। ইন্ডেক্সিং বিশ্লেষণ MLIR এর Affine Map পরিকাঠামোর উপর নির্মিত এবং HLO শব্দার্থবিদ্যা যোগ করে।

কোলেসিং

মেমরি কোলেসিং সম্পর্কে যুক্তি অ-তুচ্ছ ক্ষেত্রে সম্ভব হয়ে ওঠে, যখন আমরা জানি আউটপুটের একটি উপাদান গণনা করার জন্য ইনপুটগুলির কোন উপাদান/স্লাইস পড়া হয়।

অপারেন্ড ইউটিলাইজেশন

XLA-তে অপারেন্ড ইউটিলাইজেশন নির্দেশ করে যে নির্দেশের প্রতিটি ইনপুট কতটা ব্যবহার করা হয়েছে অনুমান করে তার আউটপুট সম্পূর্ণরূপে ব্যবহৃত হয়েছে। বর্তমানে, একটি জেনেরিক ক্ষেত্রেও ব্যবহার গণনা করা হয় না। ইন্ডেক্সিং বিশ্লেষণ সুনির্দিষ্টভাবে ব্যবহার গণনা করার অনুমতি দেয়।

টাইলিং

একটি টাইল/স্লাইস হল একটি টেনসরের হাইপার-আয়তক্ষেত্রাকার উপসেট যা অফসেট, আকার এবং স্ট্রাইড দ্বারা প্যারামিটারাইজ করা হয়। টাইল প্রচার হল অপের টাইলিং পরামিতি ব্যবহার করে অপের প্রযোজক/ভোক্তার টাইল প্যারামিটার গণনা করার একটি উপায়। ইতিমধ্যে একটি লাইব্রেরি রয়েছে যা এটি সফটম্যাক্স এবং ডটের জন্য করে। টাইল প্রচারকে আরও সাধারণ এবং শক্তিশালী করা যেতে পারে যদি এটি সূচীকরণ মানচিত্রের মাধ্যমে প্রকাশ করা হয়।

ফাংশন এবং ডোমেইন

ইন্ডেক্সিং ম্যাপ হল একটি ফাংশন f ( x ) = f ( d , r , rt ) যেটি একটি টেনসর A এর একটি মাল্টি-ইনডেক্স d কে টেনসর B এর উপাদান/ রেঞ্জে ম্যাপ করে। r প্যারামিটারটি টেনসর B তে উপস্থিত মাত্রার সূচকের পরিসরকে বোঝায়, কিন্তু টেনসর A তে নয়। প্যারামিটার rt রানটাইম মান বোঝায়, যেমন একটি সংগ্রহ অপের জন্য সূচক।

উদাহরণ স্বরূপ, যদি আমাদের tensor<2x4x8x16xf32> থেকে tensor<4x8xf32> পর্যন্ত হ্রাস করা হয়, তাহলে 2D আউটপুট থেকে 4D ইনপুটে ইন্ডেক্সিং ম্যাপ হল (d0, d1) -> (r0, d0, d1, r1) , যেখানে d_i হল ডাইমেনশন ভেরিয়েবল যা আউটপুট টেনসরের সূচকের সাথে মিলে যায়। রেঞ্জ ভেরিয়েবল r_j একাধিক মান এনকোড করে, যেমন আউটপুটের একটি (d0, d1) উপাদান গণনা করার জন্য, আমাদের ইনপুটের (r0, d0, d1, r1) উপাদানগুলির প্রয়োজন, যেখানে r0 in [0, 1] এবং r1 in [0, 15] ।

এই ম্যাপিংটি এইচএলও নির্দেশাবলীর বৈশিষ্ট্যগুলি থেকে তৈরি করা যেতে পারে বা ফিউশনের জন্য সূচী পাওয়ার জন্য অমিশ্রিত নির্দেশের ম্যাপিংগুলি তৈরি করা যেতে পারে। ম্যাপিংয়ের একটি ডোমেনও রয়েছে, যা নির্দিষ্ট করে যে টেনসরের কোন উপাদানগুলির জন্য ম্যাপিং বিদ্যমান।

f ( x ) st

lb <= g ( x ) <= ub

যেহেতু আমরা পুনর্গণনা কমাতে চাই, তাই আমাদের প্রতীকী গণনার জন্য একটি লাইব্রেরি প্রয়োজন। XLA ইতিমধ্যেই MLIR-এর উপর নির্ভর করে, তাই আমরা mlir::AffineMap-এর পরিবর্তে অন্য একটি প্রতীকী গাণিতিক লাইব্রেরি লেখার পরিবর্তে ব্যবহার করি।

একটি সাধারণ AffineMap মত দেখায়

(d0)[s0, s1] -> (s0 + 5, d0 * 2, s1 * 3 + 50)

AffineMap দুটি ধরণের প্যারামিটার রয়েছে: মাত্রা এবং প্রতীক । মাত্রাগুলি মাত্রা ভেরিয়েবল d এর সাথে মিলে যায়, চিহ্নগুলি রেঞ্জ ভেরিয়েবল r এবং RT ভেরিয়েবল rt এর সাথে মিলে যায়। AffineMap মাত্রার পরিসীমা সম্পর্কে কোনো মেটাডেটা নেই, তাই আমাদের নিজেদেরকে এই ডেটা প্রদান করতে হবে।

struct Interval {
 int64_t lower;
 int64_t upper;
};

class IndexingMap {
   // Variable represents dimension, range or runtime variable.
  struct Variable {
    Interval bounds;
    // Name of the variable is used for nicer printing.
    std::string name = "";
  };

  mlir::AffineMap affine_map_;

  // DimVars represent dimensions of a tensor or of a GPU grid.
  std::vector<Variable> dim_vars_;

  // RangeVars represent ranges of values, e.g. to compute a single element of
  // the reduction's result we need a range of values from the input tensor.
  std::vector<Variable> range_vars_;

  // RTVars represent runtime values, e.g. a dynamic offset in
  // HLO dynamic-update-slice op.
  std::vector<Variable> rt_vars_;
  llvm::DenseMap<mlir::AffineExpr, Interval> constraints_;
};

dim_vars_ ইনডেক্সিং ম্যাপের ডাইমেনশন ভেরিয়েবল d-এর জন্য ইনক্লুসিভ বক্স সীমাবদ্ধতাগুলিকে এনকোড করে, যা সাধারণত ট্রান্সপোজ, রিডুড, এলিমেন্টওয়াইজ, ডট-এর মতো অপ্সের জন্য আউটপুট টেনসরের আকারের সাথে মিলে যায়, কিন্তু কিছু ব্যতিক্রম আছে যেমন HloConcatenateInstruction ।

range_vars_ এনকোড সম্ভাব্য মান যা r প্যারামিটার নিতে পারে।

rt_vars_ রানটাইমে সম্ভাব্য মান এনকোড করে। উদাহরণস্বরূপ, অফসেট একটি 1D HloDynamicSliceInstruction এর জন্য গতিশীল। সংশ্লিষ্ট RTVar সম্ভাব্য মান 0 এবং tensor_size - slice_size - 1 মধ্যে থাকবে।

উপরোক্ত সবকটির প্রকৃত অর্থ কী তা বোঝার জন্য আসুন উদাহরণ দ্বারা অধ্যয়ন করি।

Unfused Ops জন্য মানচিত্র সূচীকরণ

উপাদান অনুসারে

এলিমেন্টওয়াইজ অপারেশনের জন্য ইন্ডেক্সিং ম্যাপ হল একটি পরিচয়।

  p0 = f32[10, 20] parameter(0)
  p1 = f32[10, 20] parameter(1)
  add = f32[10, 20] add(p0, p1)

মানচিত্র ইনপুট করার আউটপুট:

• আউটপুট -> input_i:

(d0, d1) -> (d0, d1),
domain:
d0 in [0, 9],
d1 in [0, 19]

আউটপুট মানচিত্র ইনপুট

• input_i -> আউটপুট:

(d0, d1) -> (d0, d1),
domain:
d0 in [0, 9],
d1 in [0, 19]

সম্প্রচার

সম্প্রচারের অর্থ হল যখন আমরা আউটপুটকে ইনপুটে ম্যাপ করি এবং যখন আমরা ইনপুটকে আউটপুটে ম্যাপ করি তখন কিছু মাত্রা মুছে ফেলা হয়।

p0 = f32[20] parameter(0)
bc0 = f32[10, 20, 30] broadcast(p0), dimensions={1}

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2) -> (d1),
domain:
d0 in [0, 9],
d1 in [0, 19],
d2 in [0, 29]

ইনপুট থেকে আউটপুট ম্যাপ

(d0)[s0, s1] -> (s0, d0, s1),
domain:
d0 in [0, 19],
s0 in [0, 9],
s1 in [0, 29]

মনে রাখবেন যে ইনপুট-টু-আউটপুট ম্যাপিংয়ের জন্য এখন আমাদের ডানদিকে s আছে। সেগুলি হল চিহ্ন যা মানের রেঞ্জের প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, এই বিশেষ ক্ষেত্রে ইনডেক্স d0 সহ ইনপুটের প্রতিটি উপাদান আউটপুটের 10x1x30 স্লাইসে ম্যাপ করা হয়।

ধ্রুবক এবং Iota

সুবিধামত, তাদের কোন ইনপুট পরামিতি নেই, তাই ইন্ডেক্সিং গণনা করার কিছু নেই।

ডাইনামিক স্লাইস

ডাইনামিকস্লাইস স্লাইসের মতোই, তবে অফসেটগুলি গতিশীল।

src = s32[2,2,258] parameter(0)
of1 = s32[] parameter(1)
of2 = s32[] parameter(2)
of3 = s32[] parameter(3)
ds = dynamic-slice(s32[2,2,258] src, s32[] of1, s32[] of2, s32[] of3), dynamic_slice_sizes={1, 2, 32}

src এর জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1, d2){rt0, rt1, rt2} -> (d0 + rt0, d1 + rt1, d2 + rt2),
domain:
d0 in [0, 0],
d1 in [0, 1],
d2 in [0, 31],
rt0 in [0, 1],
rt1 in [0, 0],
rt2 in [0, 226]

মনে রাখবেন যে ইনপুট-টু-আউটপুট ম্যাপিংয়ের জন্য এখন আমাদের ডানদিকে rt আছে। সেগুলি হল চিহ্ন যা রানটাইম মান প্রতিনিধিত্ব করে। উদাহরণ স্বরূপ, এই বিশেষ ক্ষেত্রে আউটপুটের প্রতিটি উপাদানের জন্য সূচক d0, d1, d2 আমরা ইনপুটের সূচক গণনা করতে of1 , of2 এবং of3 এর স্লাইস অফসেটগুলি অ্যাক্সেস করি। রানটাইম ভেরিয়েবলের ব্যবধানগুলি অনুমান করে নেওয়া হয় যে পুরো স্লাইসটি সীমানায় থাকে।

of1 , of2 এবং of3 এর জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1, d2)  -> (),
domain:
d0 in [0, 0],
d1 in [0, 1],
d2 in [0, 31]

ডাইনামিকআপডেট স্লাইস

src = s32[20,30] parameter(0)
upd = s32[5,10] parameter(1)
of1 = s32[] parameter(2)
of2 = s32[] parameter(3)
dus = s32[20,30] dynamic-update-slice(
    s32[20,30] src, s32[5,10] upd, s32[] of1, s32[] of2)

src এর জন্য ইনপুট মানচিত্রের আউটপুট তুচ্ছ। ডোমেইনকে আপডেট করা হয়নি এমন সূচকগুলিতে সীমাবদ্ধ করে এটি আরও সুনির্দিষ্ট করা যেতে পারে, তবে এখনই সূচীকরণ মানচিত্রগুলি বৈষম্যের সীমাবদ্ধতা সমর্থন করে না।

(d0, d1) -> (d0, d1),
domain:
d0 in [0, 19],
d1 in [0, 29]

upd জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1){rt0, rt1}  -> (d0 - rt0, d1 - rt1),
domain:
d0 in [0, 19],
d1 in [0, 29],
rt0 in [0, 15],
rt1 in [0, 20]

মনে রাখবেন যে ইনপুট-টু-আউটপুট ম্যাপিংয়ের জন্য এখন আমাদের ডানদিকে s আছে। সেগুলি হল চিহ্ন যা রানটাইম মান প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, এই বিশেষ ক্ষেত্রে সূচক d0, d1 সহ আউটপুটের প্রতিটি উপাদানের জন্য আমরা ইনপুটের সূচক গণনা করতে of1 এবং of2 স্লাইস অফসেটগুলি অ্যাক্সেস করি। রানটাইম ভেরিয়েবলের ব্যবধানগুলি অনুমান করে নেওয়া হয় যে পুরো স্লাইসটি সীমানায় থাকে।

of1 এবং of2 জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1)  -> (),
domain:
d0 in [0, 19],
d1 in [0, 29]

জড়ো করা

শুধুমাত্র সরলীকৃত জমায়েত সমর্থিত. [gather_simplifier] দেখুন।( https://github.com/openxla/xla/blob/main/xla/hlo/transforms/simplifiers/gather_simplifier.h )।

operand = f32[33,76,70] parameter(0)
indices = s32[1806,2] parameter(1)
gather = f32[1806,7,8,4] gather(operand, indices),
  offset_dims={1,2,3},
  collapsed_slice_dims={},
  start_index_map={0,1},
  index_vector_dim=1,
  slice_sizes={7,8,4}

operand জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1, d2, d3){rt0, rt1} -> (d1 + rt0, d2 + rt1, d3),
domain:
d0 in [0, 1805],
d1 in [0, 6],
d2 in [0, 7],
d3 in [0, 3],
rt0 in [0, 26],
rt1 in [0, 68]

মনে রাখবেন যে ইনপুট-টু-আউটপুট ম্যাপিংয়ের জন্য এখন আমাদের ডানদিকে s আছে। সেগুলি হল চিহ্ন যা রানটাইম মান প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, এই নির্দিষ্ট ক্ষেত্রে সূচক d0, d1, d2, d3 সহ আউটপুটের প্রতিটি উপাদানের জন্য আমরা indices টেনসর থেকে উপাদানগুলি (d0, 0) এবং (d0, 1) বের করি।

indices জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1, d2, d3)[s0] -> (d0, s0),
domain:
d0 in [0, 1805],
d1 in [0, 6],
d2 in [0, 7],
d3 in [0, 3],
s0 in [0, 1]

রেঞ্জ ভেরিয়েবল s0 দেখায় যে আউটপুটের একটি উপাদান গণনা করার জন্য আমাদের indices টেনসরের সম্পূর্ণ সারি (d0, *) প্রয়োজন।

স্থানান্তর

ট্রান্সপোজের জন্য ইন্ডেক্সিং ম্যাপ হল ইনপুট/আউটপুট মাত্রার একটি পরিবর্তন।

p0 = f32[3, 12288, 6, 128] parameter(0)
transpose = f32[3, 6, 128, 12288] transpose(p0), dimensions={0, 2, 3, 1}

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2, d3) -> (d0, d3, d1, d2),
domain:
d0 in [0, 2],
d1 in [0, 5],
d2 in [0, 127],
d3 in [0, 12287],

আউটপুট মানচিত্রের ইনপুট:

(d0, d1, d2, d3) -> (d0, d2, d3, d1),
domain:
d0 in [0, 2],
d1 in [0, 12287],
d2 in [0, 5],
d3 in [0, 127]

বিপরীত

বিপরীতের জন্য ইন্ডেক্সিং মানচিত্র বিপরীত মাত্রাগুলিকে upper_bound(d_i) - d_i এ পরিবর্তন করে :

p0 = f32[1, 17, 9, 9] parameter(0)
reverse = f32[1, 17, 9, 9] reverse(p0), dimensions={1, 2}

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2, d3) -> (d0, -d1 + 16, -d2 + 8, d3),
domain:
d0 in [0, 0],
d1 in [0, 16],
d2 in [0, 8],
d3 in [0, 8]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1, d2, d3) -> (d0, -d1 + 16, -d2 + 8, d3),
domain:
d0 in [0, 0],
d1 in [0, 16],
d2 in [0, 8],
d3 in [0, 8]

(বৈচিত্র্যময়) হ্রাস করা

ভ্যারিয়াডিক রিডাকশনে বেশ কয়েকটি ইনপুট এবং বেশ কয়েকটি ইনিট রয়েছে, আউটপুট থেকে ইনপুট পর্যন্ত মানচিত্র হ্রাসকৃত মাত্রা যোগ করে। সুতরাং, এটি কিছু অর্থে সম্প্রচারের বিপরীতের মতো আচরণ করে।

p0 = f32[256,10] parameter(0)
p0_init = f32[] constant(-inf)
p1 = s32[256,10] parameter(1)
p1_init = s32[] constant(0)
reduce = (f32[10], s32[10]) reduce(p0, p1, p0_init, p1_init),
  dimensions={0}, to_apply=max

মানচিত্র ইনপুট করার আউটপুট:

• আউটপুট -> input_j:

(d0)[s0] -> (s0, d0),
domain:
d0 in [0, 9],
s0 in [0, 255]

• আউটপুট -> init_j:

(d0) -> (),
domain:
d0 in [0, 9]

আউটপুট মানচিত্র ইনপুট:

• input_i -> output_j:

(d0, d1) -> (d1),
domain:
d0 in [0, 255],
d1 in [0, 9]

• init_i -> output_j:

()[s0] -> (s0),
domain:
s0 in [0, 9]

i, j = 0, ... INPUT_COUNT এর জন্য।

স্লাইস

স্লাইসের জন্য আউটপুট থেকে ইনপুট পর্যন্ত সূচীকরণের ফলে একটি স্ট্রাইডেড ইনডেক্সিং ম্যাপ তৈরি হয় যা আউটপুটের প্রতিটি উপাদানের জন্য বৈধ। ইনপুট থেকে আউটপুটে ম্যাপিং ইনপুটের উপাদানগুলির একটি স্ট্রীড রেঞ্জের মধ্যে সীমাবদ্ধ।

p0 = f32[10, 20, 50] parameter(0)
slice = f32[5, 3, 25] slice(f32[10, 20, 50] p0),
  slice={[5:10:1], [3:20:7], [0:50:2]}

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2) -> (d0 + 5, d1 * 7 + 3, d2 * 2),
domain:
d0 in [0, 4],
d1 in [0, 2],
d2 in [0, 24]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1, d2) -> (d0 - 5, (d1 - 3) floordiv 7, d2 floordiv 2),
domain:
d0 in [5, 9],
d1 in [3, 17],
d2 in [0, 48],
(d1 - 3) mod 7 in [0, 0],
d2 mod 2 in [0, 0]

পুনরায় আকার দিন

রিশেপগুলি বিভিন্ন স্বাদে আসে।

আকৃতি সঙ্কুচিত করুন

এটি এনডি থেকে 1ডিতে একটি "লিনিয়ারাইজিং" রিশেপ।

p0 = f32[4,8] parameter(0)
reshape = f32[32] reshape(p0)

ইনপুট মানচিত্র আউটপুট:

(d0) -> (d0 floordiv 8, d0 mod 8),
domain:
d0 in [0, 31]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1) -> (d0 * 8 + d1),
domain:
d0 in [0, 3],
d1 in [0, 7]

আকৃতি প্রসারিত করুন

এটি একটি বিপরীত "পতনের আকৃতি" অপশন, এটি একটি 1D ইনপুটকে ND আউটপুটে পুনরায় আকার দেয়।

p0 = f32[32] parameter(0)
reshape = f32[4, 8] reshape(p0)

ইনপুট মানচিত্র আউটপুট:

(d0, d1) -> (d0 * 8 + d1),
domain:
d0 in [0, 3],
d1 in [0, 7]

আউটপুট মানচিত্রের ইনপুট:

(d0) -> (d0 floordiv 8, d0 mod 8),
domain:
d0 in [0, 31]

সাধারণ পুনঃআকৃতি

এগুলি হল রিশেপ অপ্স যেগুলিকে একক প্রসারিত বা ভেঙে পড়া আকৃতি হিসাবে উপস্থাপন করা যায় না। এগুলিকে শুধুমাত্র 2 বা তার বেশি প্রসারিত বা ভেঙে পড়া আকারের একটি রচনা হিসাবে উপস্থাপন করা যেতে পারে।

উদাহরণ 1: লিনিয়ারাইজেশন-রেখাকরণ।

p0 = f32[4,8] parameter(0)
reshape = f32[2, 4, 4] reshape(p0)

এই রিশেপটিকে tensor<4x8xf32> থেকে tensor<32xf32> এবং তারপর tensor<2x4x4xf32> এর আকৃতি সম্প্রসারণের একটি রচনা হিসাবে উপস্থাপন করা যেতে পারে।

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2) -> (d0 * 2 + d1 floordiv 2, d2 + (d1 mod 2) * 4),
domain:
d0 in [0, 1],
d1 in [0, 3],
d2 in [0, 3]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1) -> (d0 floordiv 2, d1 floordiv 4 + (d0 mod 2) * 2, d1 mod 4),
domain:
d0 in [0, 3],
d1 in [0, 7]

উদাহরণ 2: প্রসারিত এবং সংকুচিত সাবশেপ

p0 = f32[4, 8, 12] parameter(0)
reshape = f32[32, 3, 4] reshape(p0)

এই পুনঃআকৃতি দুটি পুনঃআকৃতির একটি রচনা হিসাবে উপস্থাপন করা যেতে পারে। প্রথমটি বাইরেরতম মাত্রার tensor<4x8x12xf32> কে tensor<32x12xf32> ভেঙে ফেলে এবং দ্বিতীয়টি ভিতরেরতম মাত্রার tensor<32x12xf32> tensor<32x3x4xf32> প্রসারিত করে।

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2) -> (d0 floordiv 8, d0 mod 8, d1 * 4 + d2),
domain:
d0 in [0, 31],
d1 in [0, 2]
d2 in [0, 3]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1, d2) -> (d0 * 8 + d1, d2 floordiv 4, d2 mod 4),
domain:
d0 in [0, 3],
d1 in [0, 7],
d2 in [0, 11]

বিটকাস্ট

একটি বিটকাস্ট অপকে ট্রান্সপোজ-রিশেপ-ট্রান্সপোজের একটি ক্রম হিসাবে উপস্থাপন করা যেতে পারে। অতএব, এর সূচীকরণ মানচিত্রগুলি এই অনুক্রমের জন্য ইন্ডেক্সিং মানচিত্রের একটি সংমিশ্রণ মাত্র।

সংযুক্ত করা

কনক্যাটের জন্য আউটপুট-টু-ইনপুট ম্যাপিং সমস্ত ইনপুটগুলির জন্য সংজ্ঞায়িত করা হয়েছে, তবে অ-ওভারল্যাপিং ডোমেনগুলির সাথে, অর্থাৎ একবারে শুধুমাত্র একটি ইনপুট ব্যবহার করা হবে৷

p0 = f32[2, 5, 7] parameter(0)
p1 = f32[2, 11, 7] parameter(1)
p2 = f32[2, 17, 7] parameter(2)
ROOT concat = f32[2, 33, 7] concatenate(f32[2, 5, 7] p0, f32[2, 11, 7] p1, f32[2, 17, 7] p2), dimensions={1}

ইনপুট মানচিত্রের আউটপুট:

• আউটপুট -> ইনপুট 1:

(d0, d1, d2) -> (d0, d1, d2),
domain:
d0 in [0, 1],
d1 in [0, 4],
d2 in [0, 6]

• আউটপুট -> ইনপুট 2:

(d0, d1, d2) -> (d0, d1 - 5, d2),
domain:
d0 in [0, 1],
d1 in [5, 15],
d2 in [0, 6]

• আউটপুট -> ইনপুট 3:

(d0, d1, d2) -> (d0, d1 - 16, d2),
domain:
d0 in [0, 1],
d1 in [16, 32],
d2 in [0, 6]

আউটপুট মানচিত্রের ইনপুট:

• ইনপুট 1 -> আউটপুট:

(d0, d1, d2) -> (d0, d1, d2),
domain:
d0 in [0, 1],
d1 in [0, 4],
d2 in [0, 6]

• ইনপুট 2 -> আউটপুট:

(d0, d1, d2) -> (d0, d1 + 5, d2),
domain:
d0 in [0, 1],
d1 in [0, 10],
d2 in [0, 6]

• ইনপুট 3 -> আউটপুট:

(d0, d1, d2) -> (d0, d1 + 16, d2),
domain:
d0 in [0, 1],
d1 in [0, 16],
d2 in [0, 6]

ডট

বিন্দুর জন্য ইন্ডেক্সিং মানচিত্রগুলি হ্রাসের সাথে খুব মিল।

p0 = f32[4, 128, 256] parameter(0)
p1 = f32[4, 256, 64] parameter(1)
dot = f32[4, 128, 64] dot(p0, p1),
  lhs_batch_dims={0}, rhs_batch_dims={0},
  lhs_contracting_dims={2}, rhs_contracting_dims={1}

ইনপুট মানচিত্রের আউটপুট:

• আউটপুট -> ইনপুট_1:

(d0, d1, d2)[s0] -> (d0, d1, s0),
domain:
d0 in [0, 3],
d1 in [0, 127],
d2 in [0, 63],
s0 in [0, 255]

• আউটপুট -> ইনপুট_2:

(d0, d1, d2)[s0] -> (d0, s0, d2),
domain:
d0 in [0, 3],
d1 in [0, 127],
d2 in [0, 63],
s0 in [0, 255]

আউটপুট মানচিত্রের ইনপুট:

• input_1 -> আউটপুট:

(d0, d1, d2)[s0] -> (d0, d1, s0),
domain:
d0 in [0, 3],
d1 in [0, 127],
d2 in [0, 255],
s0 in [0, 63]

• input_2 -> আউটপুট:

(d0, d1, d2)[s0] -> (d0, s0, d1),
domain:
d0 in [0, 3],
d1 in [0, 255],
d2 in [0, 63],
s0 in [0, 127]

প্যাড

PadOp-এর ইন্ডেক্সিং হল SliceOp ইন্ডেক্সিংয়ের বিপরীত।

p0 = f32[4, 4] parameter(0)
p1 = f32[] parameter(1)
pad = f32[12, 16] pad(p0, p1), padding=1_4_1x4_8_0

প্যাডিং কনফিগারেশন 1_4_1x4_8_0 বোঝায় lowPad_highPad_interiorPad_dim_0 x lowPad_highPad_interiorPad_dim_1 ।

মানচিত্র ইনপুট করার আউটপুট:

• আউটপুট -> ইনপুট:

(d0, d1) -> ((d0 - 1) floordiv 2, d1 - 4),
domain:
d0 in [1, 7],
d1 in [4, 7],
(d0 - 1) mod 2 in [0, 0]

• আউটপুট -> init:

(d0, d1) -> (),
domain:
d0 in [0, 11],
d1 in [0, 15]

উইন্ডো হ্রাস করুন

XLA-তে ReduceWindow প্যাডিংও করে। তাই, ইনডেক্সিং ম্যাপগুলিকে ReduceWindow সূচীকরণের একটি রচনা হিসাবে গণনা করা যেতে পারে যা কোনও প্যাডিং এবং PadOp এর সূচীকরণ করে না।

c_inf = f32[] constant(-inf)
p0 = f32[1024, 514] parameter(0)
reduce-window = f32[1024, 3] reduce-window(p0, c_inf),
  window={size=1x512 pad=0_0x0_0}, to_apply=max

মানচিত্র ইনপুট করার আউটপুট:

• আউটপুট -> ইনপুট:

(d0, d1)[s0] -> (d0, d1 + s0),
domain:
d0 in [0, 1023],
d1 in [0, 2],
s0 in [0, 511]

• আউটপুট -> init:

(d0, d1) -> (),
domain:
d0 in [0, 1023],
d1 in [0, 2]

ফিউশনের জন্য ইন্ডেক্সিং ম্যাপ

ফিউশন অপের জন্য ইন্ডেক্সিং ম্যাপ হল ক্লাস্টারের প্রতিটি অপের জন্য ইন্ডেক্সিং ম্যাপের একটি সংমিশ্রণ। এটি ঘটতে পারে যে কিছু ইনপুট বিভিন্ন অ্যাক্সেস প্যাটার্ন সহ একাধিকবার পড়া হয়।

একটি ইনপুট, একাধিক ইন্ডেক্সিং ম্যাপ

এখানে p0 + transpose(p0) এর একটি উদাহরণ।

f {
  p0 = f32[1000, 1000] parameter(0)
  transpose_p0 = f32[1000, 1000]{0, 1} transpose(p0), dimensions={1, 0}
  ROOT a0 = f32[1000, 1000] add(p0, transpose_p0)
}

p0 এর জন্য আউটপুট-টু-ইনপুট ইন্ডেক্সিং মানচিত্র হবে (d0, d1) -> (d0, d1) এবং (d0, d1) -> (d1, d0) । এর অর্থ হল আউটপুটের একটি উপাদান গণনা করার জন্য আমাদের ইনপুট প্যারামিটারটি দুইবার পড়তে হবে।

একটি ইনপুট, অনুলিপি করা ইন্ডেক্সিং মানচিত্র

এমন কিছু ক্ষেত্রে আছে যখন ইনডেক্সিং মানচিত্রগুলি আসলে একই, যদিও তা অবিলম্বে স্পষ্ট নয়।

f {
  p0 = f32[20, 10, 50] parameter(0)
  lhs_transpose_1 = f32[10, 20, 50] transpose(p0), dimensions={1, 0, 2}
  lhs_e = f32[10, 20, 50] exponential(lhs_transpose_1)
  lhs_transpose_2 = f32[10, 50, 20] transpose(lhs_e), dimensions={0, 2, 1}
  rhs_transpose_1 = f32[50, 10, 20] transpose(p0), dimensions={2, 1, 0}
  rhs_log = f32[50, 10, 20] exponential(rhs_transpose_1)
  rhs_transpose_2 = f32[10, 50, 20] transpose(rhs_log), dimensions={1, 0, 2}
  ROOT add = f32[10, 50, 20] add(lhs_transpose_2, rhs_transpose_2)
}

এই ক্ষেত্রে p0 এর জন্য আউটপুট-টু-ইনপুট ইন্ডেক্সিং মানচিত্র হল (d0, d1, d2) -> (d2, d0, d1) ।

সফটম্যাক্স

softmax-এর জন্য parameter 0 জন্য আউটপুট-টু-ইনপুট ইন্ডেক্সিং মানচিত্র:

(d0, d1, d2)[s0] -> (d0, d1, s0),
domain:
d0 in [0, 1],
d1 in [0, 64],
d2 in [0, 124],
s0 in [0, 124]

এবং

(d0, d1, d2) -> (d0, d1, d2),
domain:
d0 in [0, 1],
d1 in [0, 64],
d2 in [0, 124]

যেখানে s0 ইনপুটের অভ্যন্তরীণ-সর্বাধিক মাত্রা বোঝায়।

আরও উদাহরণের জন্য indexing_analysis_test.cc দেখুন।

ইন্ডেক্সিং ম্যাপ সিম্পলিফায়ার

mlir::AffineMap আপস্ট্রিমের জন্য ডিফল্ট সরলীকরণ মাত্রা/চিহ্নের পরিসর সম্পর্কে কোনো অনুমান করতে পারে না। অতএব, এটি দক্ষতার সাথে mod এবং div দিয়ে অভিব্যক্তিকে সরল করতে পারে না।

আমরা অ্যাফাইন ম্যাপে সাব-অভিব্যক্তির নিম্ন এবং উপরের সীমা সম্পর্কে জ্ঞান লাভ করতে পারি যাতে তাদের আরও সহজ করা যায়।

সরলীকরণকারী নিম্নলিখিত অভিব্যক্তিগুলি পুনরায় লিখতে পারে।

1. (d0, d1) -> (d0 + d1 floordiv 16, d1 mod 16) d- এর জন্য [0, 6] x [0, 14] হয়ে যায় (d0, d1) -> (d0, d1)
2. (d0, d1, d2) -> ((100d0 + 10d1 + d2) floorDiv 100, ((100d0 + 10d1 + d2) mod 100) floordiv 10, d2 mod 10) di in [0, 9] এর জন্য floordiv 10, d2 mod 10) হয়ে যায় (d0, d1, d2) -> (d0, d1, d2) ।
3. (d0, d1, d2) -> ((16d0 + 4d1 + d2) floordiv 8, (16d0 + 4d1 + d2) mod 8) d_i in [0, 9] হয়ে যায় (d0, d1, d2) -> (2d0 + (4d1 + d2) floordiv 8,(4d1 + d2) mod 8) ।
4. (d0, d1) -> (-(-11d0 - d1 + 109) floordiv 11 + 9) d এর জন্য [0, 9] x [0, 10] হয়ে যায় (d0, d1) -> (d0) ।

ইন্ডেক্সিং ম্যাপ সিম্পলিফায়ার আমাদের বুঝতে দেয় যে HLO-তে কিছু চেইন্ড রিশেপ একে অপরকে বাতিল করে।

p0 = f32[10, 10, 10] parameter(0)
reshape1 = f32[50, 20] reshape(p0)
reshape2 = f32[10, 10, 10] reshape(reshape1)

ইনডেক্সিং ম্যাপ এবং তাদের সরলীকরণের পরে আমরা পাব

(d0, d1, d2) -> (d0, d1, d2) ।

ইন্ডেক্সিং মানচিত্র সরলীকরণ সীমাবদ্ধতাগুলিকেও সরল করে।

1. lower_bound <= affine_expr (floordiv, +, -, *) constant <= upper_bound প্রকারের সীমাবদ্ধতা updated_lower_bound <= affine_expr <= updated_upped_bound হিসাবে পুনরায় লেখা হয়।
2. যে সীমাবদ্ধতাগুলি সর্বদা সন্তুষ্ট থাকে, যেমন d0 + s0 in [0, 20] এর জন্য d0 in [0, 5] এবং s0 in [1, 3] বাদ দেওয়া হয়।
3. সীমাবদ্ধতার মধ্যে Affine এক্সপ্রেশনগুলি উপরের সূচীকৃত affine মানচিত্র হিসাবে অপ্টিমাইজ করা হয়েছে।

আরও উদাহরণের জন্য indexing_map_test.cc দেখুন।

এই নথিটি HLO সূচী বিশ্লেষণের বর্ণনা করে, যা আপনাকে HLO অপ্সের জন্য প্রতীকীভাবে সূচীকরণ মানচিত্র গণনা করতে দেয়। ইন্ডেক্সিং ম্যাপ হল এমন একটি ফাংশন যা একটি টেনসরের সূচককে অন্যটির সূচকে ম্যাপ করে, যেমন একটি এইচএলও নির্দেশনা আউটপুটের সূচকগুলিকে এইচএলও নির্দেশনা ইনপুটগুলির সূচকে বা এর বিপরীতে।

উদাহরণ

tensor<20xf32> থেকে tensor<10x20x30xf32> সম্প্রচারের জন্য

p0 = f32[20] parameter(0)
bc0 = f32[10, 20, 30] broadcast(p0), dimensions={1}

আউটপুট থেকে ইনপুট পর্যন্ত ইন্ডেক্সিং ম্যাপ হল (i, j, k) -> (j) i in [0, 10] , j in [0, 20] এবং k in [0, 30] ।

প্রেরণা

XLA GPU সমন্বিতকরণ, অপারেন্ড ইউটিলাইজেশন, এবং টাইলিং স্কিম (নীচে আরও বিশদ বিবরণ) সম্পর্কে যুক্তি দেওয়ার জন্য বেশ কয়েকটি বেসপোক সমাধান ব্যবহার করে। ইন্ডেক্সিং বিশ্লেষণের লক্ষ্য হল এই ধরনের ব্যবহারের ক্ষেত্রে একটি পুনঃব্যবহারযোগ্য উপাদান প্রদান করা। ইন্ডেক্সিং বিশ্লেষণ MLIR এর Affine Map পরিকাঠামোর উপর নির্মিত এবং HLO শব্দার্থবিদ্যা যোগ করে।

কোলেসিং

মেমরি কোলেসিং সম্পর্কে যুক্তি অ-তুচ্ছ ক্ষেত্রে সম্ভব হয়ে ওঠে, যখন আমরা জানি আউটপুটের একটি উপাদান গণনা করার জন্য ইনপুটগুলির কোন উপাদান/স্লাইস পড়া হয়।

অপারেন্ড ইউটিলাইজেশন

XLA-তে অপারেন্ড ইউটিলাইজেশন নির্দেশ করে যে নির্দেশের প্রতিটি ইনপুট কতটা ব্যবহার করা হয়েছে অনুমান করে তার আউটপুট সম্পূর্ণরূপে ব্যবহৃত হয়েছে। বর্তমানে, একটি জেনেরিক ক্ষেত্রেও ব্যবহার গণনা করা হয় না। ইন্ডেক্সিং বিশ্লেষণ সুনির্দিষ্টভাবে ব্যবহার গণনা করার অনুমতি দেয়।

টাইলিং

একটি টাইল/স্লাইস হল একটি টেনসরের হাইপার-আয়তক্ষেত্রাকার উপসেট যা অফসেট, আকার এবং স্ট্রাইড দ্বারা প্যারামিটারাইজ করা হয়। টাইল প্রচার হল অপের টাইলিং পরামিতি ব্যবহার করে অপের প্রযোজক/ভোক্তার টাইল প্যারামিটার গণনা করার একটি উপায়। ইতিমধ্যে একটি লাইব্রেরি রয়েছে যা এটি সফটম্যাক্স এবং ডটের জন্য করে। টাইল প্রচারকে আরও সাধারণ এবং শক্তিশালী করা যেতে পারে যদি এটি সূচীকরণ মানচিত্রের মাধ্যমে প্রকাশ করা হয়।

ফাংশন এবং ডোমেইন

ইন্ডেক্সিং ম্যাপ হল একটি ফাংশন f ( x ) = f ( d , r , rt ) যেটি একটি টেনসর A এর একটি মাল্টি-ইনডেক্স d কে টেনসর B এর উপাদান/ রেঞ্জে ম্যাপ করে। r প্যারামিটারটি টেনসর B তে উপস্থিত মাত্রার সূচকের পরিসরকে বোঝায়, কিন্তু টেনসর A তে নয়। প্যারামিটার rt রানটাইম মান বোঝায়, যেমন একটি সংগ্রহ অপের জন্য সূচক।

উদাহরণ স্বরূপ, যদি আমাদের tensor<2x4x8x16xf32> থেকে tensor<4x8xf32> পর্যন্ত হ্রাস করা হয়, তাহলে 2D আউটপুট থেকে 4D ইনপুটে ইন্ডেক্সিং ম্যাপ হল (d0, d1) -> (r0, d0, d1, r1) , যেখানে d_i হল ডাইমেনশন ভেরিয়েবল যা আউটপুট টেনসরের সূচকের সাথে মিলে যায়। রেঞ্জ ভেরিয়েবল r_j একাধিক মান এনকোড করে, যেমন আউটপুটের একটি (d0, d1) উপাদান গণনা করার জন্য, আমাদের ইনপুটের (r0, d0, d1, r1) উপাদানগুলির প্রয়োজন, যেখানে r0 in [0, 1] এবং r1 in [0, 15] ।

এই ম্যাপিংটি এইচএলও নির্দেশাবলীর বৈশিষ্ট্যগুলি থেকে তৈরি করা যেতে পারে বা ফিউশনের জন্য সূচী পাওয়ার জন্য অমিশ্রিত নির্দেশের ম্যাপিংগুলি তৈরি করা যেতে পারে। ম্যাপিংয়ের একটি ডোমেনও রয়েছে, যা নির্দিষ্ট করে যে টেনসরের কোন উপাদানগুলির জন্য ম্যাপিং বিদ্যমান।

f ( x ) st

lb <= g ( x ) <= ub

যেহেতু আমরা পুনর্গণনা কমাতে চাই, তাই আমাদের প্রতীকী গণনার জন্য একটি লাইব্রেরি প্রয়োজন। XLA ইতিমধ্যেই MLIR-এর উপর নির্ভর করে, তাই আমরা mlir::AffineMap-এর পরিবর্তে অন্য একটি প্রতীকী গাণিতিক লাইব্রেরি লেখার পরিবর্তে ব্যবহার করি।

একটি সাধারণ AffineMap মত দেখায়

(d0)[s0, s1] -> (s0 + 5, d0 * 2, s1 * 3 + 50)

AffineMap দুটি ধরণের প্যারামিটার রয়েছে: মাত্রা এবং প্রতীক । মাত্রাগুলি মাত্রা ভেরিয়েবল d এর সাথে মিলে যায়, চিহ্নগুলি রেঞ্জ ভেরিয়েবল r এবং RT ভেরিয়েবল rt এর সাথে মিলে যায়। AffineMap মাত্রার পরিসীমা সম্পর্কে কোনো মেটাডেটা নেই, তাই আমাদের নিজেদেরকে এই ডেটা প্রদান করতে হবে।

struct Interval {
 int64_t lower;
 int64_t upper;
};

class IndexingMap {
   // Variable represents dimension, range or runtime variable.
  struct Variable {
    Interval bounds;
    // Name of the variable is used for nicer printing.
    std::string name = "";
  };

  mlir::AffineMap affine_map_;

  // DimVars represent dimensions of a tensor or of a GPU grid.
  std::vector<Variable> dim_vars_;

  // RangeVars represent ranges of values, e.g. to compute a single element of
  // the reduction's result we need a range of values from the input tensor.
  std::vector<Variable> range_vars_;

  // RTVars represent runtime values, e.g. a dynamic offset in
  // HLO dynamic-update-slice op.
  std::vector<Variable> rt_vars_;
  llvm::DenseMap<mlir::AffineExpr, Interval> constraints_;
};

dim_vars_ ইনডেক্সিং ম্যাপের ডাইমেনশন ভেরিয়েবল d-এর জন্য ইনক্লুসিভ বক্স সীমাবদ্ধতাগুলিকে এনকোড করে, যা সাধারণত ট্রান্সপোজ, রিডুড, এলিমেন্টওয়াইজ, ডট-এর মতো অপ্সের জন্য আউটপুট টেনসরের আকারের সাথে মিলে যায়, কিন্তু কিছু ব্যতিক্রম আছে যেমন HloConcatenateInstruction ।

range_vars_ এনকোড সম্ভাব্য মান যা r প্যারামিটার নিতে পারে।

rt_vars_ রানটাইমে সম্ভাব্য মান এনকোড করে। উদাহরণস্বরূপ, অফসেট একটি 1D HloDynamicSliceInstruction এর জন্য গতিশীল। সংশ্লিষ্ট RTVar সম্ভাব্য মান 0 এবং tensor_size - slice_size - 1 মধ্যে থাকবে।

উপরোক্ত সবকটির প্রকৃত অর্থ কী তা বোঝার জন্য আসুন উদাহরণ দ্বারা অধ্যয়ন করি।

Unfused Ops জন্য মানচিত্র সূচীকরণ

উপাদান অনুসারে

এলিমেন্টওয়াইজ অপারেশনের জন্য ইন্ডেক্সিং ম্যাপ হল একটি পরিচয়।

  p0 = f32[10, 20] parameter(0)
  p1 = f32[10, 20] parameter(1)
  add = f32[10, 20] add(p0, p1)

মানচিত্র ইনপুট করার আউটপুট:

• আউটপুট -> input_i:

(d0, d1) -> (d0, d1),
domain:
d0 in [0, 9],
d1 in [0, 19]

আউটপুট মানচিত্র ইনপুট

• input_i -> আউটপুট:

(d0, d1) -> (d0, d1),
domain:
d0 in [0, 9],
d1 in [0, 19]

সম্প্রচার

সম্প্রচারের অর্থ হল যখন আমরা আউটপুটকে ইনপুটে ম্যাপ করি এবং যখন আমরা ইনপুটকে আউটপুটে ম্যাপ করি তখন কিছু মাত্রা মুছে ফেলা হয়।

p0 = f32[20] parameter(0)
bc0 = f32[10, 20, 30] broadcast(p0), dimensions={1}

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2) -> (d1),
domain:
d0 in [0, 9],
d1 in [0, 19],
d2 in [0, 29]

ইনপুট থেকে আউটপুট ম্যাপ

(d0)[s0, s1] -> (s0, d0, s1),
domain:
d0 in [0, 19],
s0 in [0, 9],
s1 in [0, 29]

মনে রাখবেন যে ইনপুট-টু-আউটপুট ম্যাপিংয়ের জন্য এখন আমাদের ডানদিকে s আছে। সেগুলি হল চিহ্ন যা মানের রেঞ্জের প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, এই বিশেষ ক্ষেত্রে ইনডেক্স d0 সহ ইনপুটের প্রতিটি উপাদান আউটপুটের 10x1x30 স্লাইসে ম্যাপ করা হয়।

ধ্রুবক এবং Iota

সুবিধামত, তাদের কোন ইনপুট পরামিতি নেই, তাই ইন্ডেক্সিং গণনা করার কিছু নেই।

ডাইনামিক স্লাইস

ডাইনামিকস্লাইস স্লাইসের মতোই, তবে অফসেটগুলি গতিশীল।

src = s32[2,2,258] parameter(0)
of1 = s32[] parameter(1)
of2 = s32[] parameter(2)
of3 = s32[] parameter(3)
ds = dynamic-slice(s32[2,2,258] src, s32[] of1, s32[] of2, s32[] of3), dynamic_slice_sizes={1, 2, 32}

src এর জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1, d2){rt0, rt1, rt2} -> (d0 + rt0, d1 + rt1, d2 + rt2),
domain:
d0 in [0, 0],
d1 in [0, 1],
d2 in [0, 31],
rt0 in [0, 1],
rt1 in [0, 0],
rt2 in [0, 226]

মনে রাখবেন যে ইনপুট-টু-আউটপুট ম্যাপিংয়ের জন্য এখন আমাদের ডানদিকে rt আছে। সেগুলি হল চিহ্ন যা রানটাইম মান প্রতিনিধিত্ব করে। উদাহরণ স্বরূপ, এই বিশেষ ক্ষেত্রে আউটপুটের প্রতিটি উপাদানের জন্য সূচক d0, d1, d2 আমরা ইনপুটের সূচক গণনা করতে of1 , of2 এবং of3 এর স্লাইস অফসেটগুলি অ্যাক্সেস করি। রানটাইম ভেরিয়েবলের ব্যবধানগুলি অনুমান করে নেওয়া হয় যে পুরো স্লাইসটি সীমানায় থাকে।

of1 , of2 এবং of3 এর জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1, d2)  -> (),
domain:
d0 in [0, 0],
d1 in [0, 1],
d2 in [0, 31]

ডাইনামিকআপডেট স্লাইস

src = s32[20,30] parameter(0)
upd = s32[5,10] parameter(1)
of1 = s32[] parameter(2)
of2 = s32[] parameter(3)
dus = s32[20,30] dynamic-update-slice(
    s32[20,30] src, s32[5,10] upd, s32[] of1, s32[] of2)

src এর জন্য ইনপুট মানচিত্রের আউটপুট তুচ্ছ। ডোমেইনকে আপডেট করা হয়নি এমন সূচকগুলিতে সীমাবদ্ধ করে এটি আরও সুনির্দিষ্ট করা যেতে পারে, তবে এখনই সূচীকরণ মানচিত্রগুলি বৈষম্যের সীমাবদ্ধতা সমর্থন করে না।

(d0, d1) -> (d0, d1),
domain:
d0 in [0, 19],
d1 in [0, 29]

upd জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1){rt0, rt1}  -> (d0 - rt0, d1 - rt1),
domain:
d0 in [0, 19],
d1 in [0, 29],
rt0 in [0, 15],
rt1 in [0, 20]

মনে রাখবেন যে ইনপুট-টু-আউটপুট ম্যাপিংয়ের জন্য এখন আমাদের ডানদিকে s আছে। সেগুলি হল চিহ্ন যা রানটাইম মান প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, এই বিশেষ ক্ষেত্রে সূচক d0, d1 সহ আউটপুটের প্রতিটি উপাদানের জন্য আমরা ইনপুটের সূচক গণনা করতে of1 এবং of2 স্লাইস অফসেটগুলি অ্যাক্সেস করি। রানটাইম ভেরিয়েবলের ব্যবধানগুলি অনুমান করে নেওয়া হয় যে পুরো স্লাইসটি সীমানায় থাকে।

of1 এবং of2 জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1)  -> (),
domain:
d0 in [0, 19],
d1 in [0, 29]

জড়ো করা

শুধুমাত্র সরলীকৃত জমায়েত সমর্থিত. [gather_simplifier] দেখুন।( https://github.com/openxla/xla/blob/main/xla/hlo/transforms/simplifiers/gather_simplifier.h )।

operand = f32[33,76,70] parameter(0)
indices = s32[1806,2] parameter(1)
gather = f32[1806,7,8,4] gather(operand, indices),
  offset_dims={1,2,3},
  collapsed_slice_dims={},
  start_index_map={0,1},
  index_vector_dim=1,
  slice_sizes={7,8,4}

operand জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1, d2, d3){rt0, rt1} -> (d1 + rt0, d2 + rt1, d3),
domain:
d0 in [0, 1805],
d1 in [0, 6],
d2 in [0, 7],
d3 in [0, 3],
rt0 in [0, 26],
rt1 in [0, 68]

মনে রাখবেন যে ইনপুট-টু-আউটপুট ম্যাপিংয়ের জন্য এখন আমাদের ডানদিকে s আছে। সেগুলি হল চিহ্ন যা রানটাইম মান প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, এই নির্দিষ্ট ক্ষেত্রে সূচক d0, d1, d2, d3 সহ আউটপুটের প্রতিটি উপাদানের জন্য আমরা indices টেনসর থেকে উপাদানগুলি (d0, 0) এবং (d0, 1) বের করি।

indices জন্য ইনপুট ম্যাপে আউটপুট:

(d0, d1, d2, d3)[s0] -> (d0, s0),
domain:
d0 in [0, 1805],
d1 in [0, 6],
d2 in [0, 7],
d3 in [0, 3],
s0 in [0, 1]

রেঞ্জ ভেরিয়েবল s0 দেখায় যে আউটপুটের একটি উপাদান গণনা করার জন্য আমাদের indices টেনসরের সম্পূর্ণ সারি (d0, *) প্রয়োজন।

স্থানান্তর

ট্রান্সপোজের জন্য ইন্ডেক্সিং ম্যাপ হল ইনপুট/আউটপুট মাত্রার একটি পরিবর্তন।

p0 = f32[3, 12288, 6, 128] parameter(0)
transpose = f32[3, 6, 128, 12288] transpose(p0), dimensions={0, 2, 3, 1}

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2, d3) -> (d0, d3, d1, d2),
domain:
d0 in [0, 2],
d1 in [0, 5],
d2 in [0, 127],
d3 in [0, 12287],

আউটপুট মানচিত্রের ইনপুট:

(d0, d1, d2, d3) -> (d0, d2, d3, d1),
domain:
d0 in [0, 2],
d1 in [0, 12287],
d2 in [0, 5],
d3 in [0, 127]

বিপরীত

বিপরীতের জন্য ইন্ডেক্সিং মানচিত্র বিপরীত মাত্রাগুলিকে upper_bound(d_i) - d_i এ পরিবর্তন করে :

p0 = f32[1, 17, 9, 9] parameter(0)
reverse = f32[1, 17, 9, 9] reverse(p0), dimensions={1, 2}

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2, d3) -> (d0, -d1 + 16, -d2 + 8, d3),
domain:
d0 in [0, 0],
d1 in [0, 16],
d2 in [0, 8],
d3 in [0, 8]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1, d2, d3) -> (d0, -d1 + 16, -d2 + 8, d3),
domain:
d0 in [0, 0],
d1 in [0, 16],
d2 in [0, 8],
d3 in [0, 8]

(বৈচিত্র্যময়) হ্রাস করা

ভ্যারিয়াডিক রিডাকশনে বেশ কয়েকটি ইনপুট এবং বেশ কয়েকটি ইনিট রয়েছে, আউটপুট থেকে ইনপুট পর্যন্ত মানচিত্র হ্রাসকৃত মাত্রা যোগ করে। সুতরাং, এটি কিছু অর্থে সম্প্রচারের বিপরীতের মতো আচরণ করে।

p0 = f32[256,10] parameter(0)
p0_init = f32[] constant(-inf)
p1 = s32[256,10] parameter(1)
p1_init = s32[] constant(0)
reduce = (f32[10], s32[10]) reduce(p0, p1, p0_init, p1_init),
  dimensions={0}, to_apply=max

মানচিত্র ইনপুট করার আউটপুট:

• আউটপুট -> input_j:

(d0)[s0] -> (s0, d0),
domain:
d0 in [0, 9],
s0 in [0, 255]

• আউটপুট -> init_j:

(d0) -> (),
domain:
d0 in [0, 9]

আউটপুট মানচিত্র ইনপুট:

• input_i -> output_j:

(d0, d1) -> (d1),
domain:
d0 in [0, 255],
d1 in [0, 9]

• init_i -> output_j:

()[s0] -> (s0),
domain:
s0 in [0, 9]

i, j = 0, ... INPUT_COUNT এর জন্য।

স্লাইস

স্লাইসের জন্য আউটপুট থেকে ইনপুট পর্যন্ত সূচীকরণের ফলে একটি স্ট্রাইডেড ইনডেক্সিং ম্যাপ তৈরি হয় যা আউটপুটের প্রতিটি উপাদানের জন্য বৈধ। ইনপুট থেকে আউটপুটে ম্যাপিং ইনপুটের উপাদানগুলির একটি স্ট্রীড রেঞ্জের মধ্যে সীমাবদ্ধ।

p0 = f32[10, 20, 50] parameter(0)
slice = f32[5, 3, 25] slice(f32[10, 20, 50] p0),
  slice={[5:10:1], [3:20:7], [0:50:2]}

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2) -> (d0 + 5, d1 * 7 + 3, d2 * 2),
domain:
d0 in [0, 4],
d1 in [0, 2],
d2 in [0, 24]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1, d2) -> (d0 - 5, (d1 - 3) floordiv 7, d2 floordiv 2),
domain:
d0 in [5, 9],
d1 in [3, 17],
d2 in [0, 48],
(d1 - 3) mod 7 in [0, 0],
d2 mod 2 in [0, 0]

পুনরায় আকার দিন

রিশেপগুলি বিভিন্ন স্বাদে আসে।

আকৃতি সঙ্কুচিত করুন

এটি এনডি থেকে 1ডিতে একটি "লিনিয়ারাইজিং" রিশেপ।

p0 = f32[4,8] parameter(0)
reshape = f32[32] reshape(p0)

ইনপুট মানচিত্র আউটপুট:

(d0) -> (d0 floordiv 8, d0 mod 8),
domain:
d0 in [0, 31]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1) -> (d0 * 8 + d1),
domain:
d0 in [0, 3],
d1 in [0, 7]

আকৃতি প্রসারিত করুন

এটি একটি বিপরীত "পতনের আকৃতি" অপশন, এটি একটি 1D ইনপুটকে ND আউটপুটে পুনরায় আকার দেয়।

p0 = f32[32] parameter(0)
reshape = f32[4, 8] reshape(p0)

ইনপুট মানচিত্র আউটপুট:

(d0, d1) -> (d0 * 8 + d1),
domain:
d0 in [0, 3],
d1 in [0, 7]

আউটপুট মানচিত্রের ইনপুট:

(d0) -> (d0 floordiv 8, d0 mod 8),
domain:
d0 in [0, 31]

সাধারণ পুনঃআকৃতি

এগুলি হল রিশেপ অপ্স যেগুলিকে একক প্রসারিত বা ভেঙে পড়া আকৃতি হিসাবে উপস্থাপন করা যায় না। এগুলিকে শুধুমাত্র 2 বা তার বেশি প্রসারিত বা ভেঙে পড়া আকারের একটি রচনা হিসাবে উপস্থাপন করা যেতে পারে।

উদাহরণ 1: লিনিয়ারাইজেশন-রেখাকরণ।

p0 = f32[4,8] parameter(0)
reshape = f32[2, 4, 4] reshape(p0)

এই রিশেপটিকে tensor<4x8xf32> থেকে tensor<32xf32> এবং তারপর tensor<2x4x4xf32> এর আকৃতি সম্প্রসারণের একটি রচনা হিসাবে উপস্থাপন করা যেতে পারে।

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2) -> (d0 * 2 + d1 floordiv 2, d2 + (d1 mod 2) * 4),
domain:
d0 in [0, 1],
d1 in [0, 3],
d2 in [0, 3]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1) -> (d0 floordiv 2, d1 floordiv 4 + (d0 mod 2) * 2, d1 mod 4),
domain:
d0 in [0, 3],
d1 in [0, 7]

উদাহরণ 2: প্রসারিত এবং সংকুচিত সাবশেপ

p0 = f32[4, 8, 12] parameter(0)
reshape = f32[32, 3, 4] reshape(p0)

এই পুনঃআকৃতি দুটি পুনঃআকৃতির একটি রচনা হিসাবে উপস্থাপন করা যেতে পারে। প্রথমটি বাইরেরতম মাত্রার tensor<4x8x12xf32> কে tensor<32x12xf32> ভেঙে ফেলে এবং দ্বিতীয়টি ভিতরেরতম মাত্রার tensor<32x12xf32> tensor<32x3x4xf32> প্রসারিত করে।

ইনপুট মানচিত্র আউটপুট:

(d0, d1, d2) -> (d0 floordiv 8, d0 mod 8, d1 * 4 + d2),
domain:
d0 in [0, 31],
d1 in [0, 2]
d2 in [0, 3]

আউটপুট মানচিত্রের ইনপুট:

(d0, d1, d2) -> (d0 * 8 + d1, d2 floordiv 4, d2 mod 4),
domain:
d0 in [0, 3],
d1 in [0, 7],
d2 in [0, 11]

বিটকাস্ট

একটি বিটকাস্ট অপকে ট্রান্সপোজ-রিশেপ-ট্রান্সপোজের একটি ক্রম হিসাবে উপস্থাপন করা যেতে পারে। অতএব, এর সূচীকরণ মানচিত্রগুলি এই অনুক্রমের জন্য ইন্ডেক্সিং মানচিত্রের একটি সংমিশ্রণ মাত্র।

সংযুক্ত করা

কনক্যাটের জন্য আউটপুট-টু-ইনপুট ম্যাপিং সমস্ত ইনপুটগুলির জন্য সংজ্ঞায়িত করা হয়েছে, তবে অ-ওভারল্যাপিং ডোমেনগুলির সাথে, অর্থাৎ একবারে শুধুমাত্র একটি ইনপুট ব্যবহার করা হবে৷

p0 = f32[2, 5, 7] parameter(0)
p1 = f32[2, 11, 7] parameter(1)
p2 = f32[2, 17, 7] parameter(2)
ROOT concat = f32[2, 33, 7] concatenate(f32[2, 5, 7] p0, f32[2, 11, 7] p1, f32[2, 17, 7] p2), dimensions={1}

ইনপুট মানচিত্রের আউটপুট:

• আউটপুট -> ইনপুট 1:

(d0, d1, d2) -> (d0, d1, d2),
domain:
d0 in [0, 1],
d1 in [0, 4],
d2 in [0, 6]

• আউটপুট -> ইনপুট 2:

(d0, d1, d2) -> (d0, d1 - 5, d2),
domain:
d0 in [0, 1],
d1 in [5, 15],
d2 in [0, 6]

• আউটপুট -> ইনপুট 3:

(d0, d1, d2) -> (d0, d1 - 16, d2),
domain:
d0 in [0, 1],
d1 in [16, 32],
d2 in [0, 6]

আউটপুট মানচিত্রের ইনপুট:

• ইনপুট 1 -> আউটপুট:

(d0, d1, d2) -> (d0, d1, d2),
domain:
d0 in [0, 1],
d1 in [0, 4],
d2 in [0, 6]

• ইনপুট 2 -> আউটপুট:

(d0, d1, d2) -> (d0, d1 + 5, d2),
domain:
d0 in [0, 1],
d1 in [0, 10],
d2 in [0, 6]

• ইনপুট 3 -> আউটপুট:

(d0, d1, d2) -> (d0, d1 + 16, d2),
domain:
d0 in [0, 1],
d1 in [0, 16],
d2 in [0, 6]

ডট

বিন্দুর জন্য ইন্ডেক্সিং মানচিত্রগুলি হ্রাসের সাথে খুব মিল।

p0 = f32[4, 128, 256] parameter(0)
p1 = f32[4, 256, 64] parameter(1)
dot = f32[4, 128, 64] dot(p0, p1),
  lhs_batch_dims={0}, rhs_batch_dims={0},
  lhs_contracting_dims={2}, rhs_contracting_dims={1}

ইনপুট মানচিত্রের আউটপুট:

• আউটপুট -> ইনপুট_1:

(d0, d1, d2)[s0] -> (d0, d1, s0),
domain:
d0 in [0, 3],
d1 in [0, 127],
d2 in [0, 63],
s0 in [0, 255]

• আউটপুট -> ইনপুট_2:

(d0, d1, d2)[s0] -> (d0, s0, d2),
domain:
d0 in [0, 3],
d1 in [0, 127],
d2 in [0, 63],
s0 in [0, 255]

আউটপুট মানচিত্রের ইনপুট:

• input_1 -> আউটপুট:

(d0, d1, d2)[s0] -> (d0, d1, s0),
domain:
d0 in [0, 3],
d1 in [0, 127],
d2 in [0, 255],
s0 in [0, 63]

• input_2 -> আউটপুট:

(d0, d1, d2)[s0] -> (d0, s0, d1),
domain:
d0 in [0, 3],
d1 in [0, 255],
d2 in [0, 63],
s0 in [0, 127]

প্যাড

PadOp-এর ইন্ডেক্সিং হল SliceOp ইন্ডেক্সিংয়ের বিপরীত।

p0 = f32[4, 4] parameter(0)
p1 = f32[] parameter(1)
pad = f32[12, 16] pad(p0, p1), padding=1_4_1x4_8_0

প্যাডিং কনফিগারেশন 1_4_1x4_8_0 বোঝায় lowPad_highPad_interiorPad_dim_0 x lowPad_highPad_interiorPad_dim_1 ।

মানচিত্র ইনপুট করার আউটপুট:

• আউটপুট -> ইনপুট:

(d0, d1) -> ((d0 - 1) floordiv 2, d1 - 4),
domain:
d0 in [1, 7],
d1 in [4, 7],
(d0 - 1) mod 2 in [0, 0]

• আউটপুট -> init:

(d0, d1) -> (),
domain:
d0 in [0, 11],
d1 in [0, 15]

উইন্ডো হ্রাস করুন

XLA-তে ReduceWindow প্যাডিংও করে। তাই, ইনডেক্সিং ম্যাপগুলিকে ReduceWindow সূচীকরণের একটি রচনা হিসাবে গণনা করা যেতে পারে যা কোনও প্যাডিং এবং PadOp এর সূচীকরণ করে না।

c_inf = f32[] constant(-inf)
p0 = f32[1024, 514] parameter(0)
reduce-window = f32[1024, 3] reduce-window(p0, c_inf),
  window={size=1x512 pad=0_0x0_0}, to_apply=max

মানচিত্র ইনপুট করার আউটপুট:

• আউটপুট -> ইনপুট:

(d0, d1)[s0] -> (d0, d1 + s0),
domain:
d0 in [0, 1023],
d1 in [0, 2],
s0 in [0, 511]

• আউটপুট -> init:

(d0, d1) -> (),
domain:
d0 in [0, 1023],
d1 in [0, 2]

ফিউশনের জন্য ইন্ডেক্সিং ম্যাপ

ফিউশন অপের জন্য ইন্ডেক্সিং ম্যাপ হল ক্লাস্টারের প্রতিটি অপের জন্য ইন্ডেক্সিং ম্যাপের একটি সংমিশ্রণ। এটি ঘটতে পারে যে কিছু ইনপুট বিভিন্ন অ্যাক্সেস প্যাটার্ন সহ একাধিকবার পড়া হয়।

একটি ইনপুট, একাধিক ইন্ডেক্সিং ম্যাপ

এখানে p0 + transpose(p0) এর একটি উদাহরণ।

f {
  p0 = f32[1000, 1000] parameter(0)
  transpose_p0 = f32[1000, 1000]{0, 1} transpose(p0), dimensions={1, 0}
  ROOT a0 = f32[1000, 1000] add(p0, transpose_p0)
}

p0 এর জন্য আউটপুট-টু-ইনপুট ইন্ডেক্সিং মানচিত্র হবে (d0, d1) -> (d0, d1) এবং (d0, d1) -> (d1, d0) । এর অর্থ হল আউটপুটের একটি উপাদান গণনা করার জন্য আমাদের ইনপুট প্যারামিটারটি দুইবার পড়তে হবে।

একটি ইনপুট, অনুলিপি করা ইন্ডেক্সিং মানচিত্র

এমন কিছু ক্ষেত্রে আছে যখন ইনডেক্সিং মানচিত্রগুলি আসলে একই, যদিও তা অবিলম্বে স্পষ্ট নয়।

f {
  p0 = f32[20, 10, 50] parameter(0)
  lhs_transpose_1 = f32[10, 20, 50] transpose(p0), dimensions={1, 0, 2}
  lhs_e = f32[10, 20, 50] exponential(lhs_transpose_1)
  lhs_transpose_2 = f32[10, 50, 20] transpose(lhs_e), dimensions={0, 2, 1}
  rhs_transpose_1 = f32[50, 10, 20] transpose(p0), dimensions={2, 1, 0}
  rhs_log = f32[50, 10, 20] exponential(rhs_transpose_1)
  rhs_transpose_2 = f32[10, 50, 20] transpose(rhs_log), dimensions={1, 0, 2}
  ROOT add = f32[10, 50, 20] add(lhs_transpose_2, rhs_transpose_2)
}

এই ক্ষেত্রে p0 এর জন্য আউটপুট-টু-ইনপুট ইন্ডেক্সিং মানচিত্র হল (d0, d1, d2) -> (d2, d0, d1) ।

সফটম্যাক্স

softmax-এর জন্য parameter 0 জন্য আউটপুট-টু-ইনপুট ইন্ডেক্সিং মানচিত্র:

(d0, d1, d2)[s0] -> (d0, d1, s0),
domain:
d0 in [0, 1],
d1 in [0, 64],
d2 in [0, 124],
s0 in [0, 124]

এবং

(d0, d1, d2) -> (d0, d1, d2),
domain:
d0 in [0, 1],
d1 in [0, 64],
d2 in [0, 124]

যেখানে s0 ইনপুটের অভ্যন্তরীণ-সর্বাধিক মাত্রা বোঝায়।

আরও উদাহরণের জন্য indexing_analysis_test.cc দেখুন।

ইন্ডেক্সিং ম্যাপ সিম্পলিফায়ার

mlir::AffineMap আপস্ট্রিমের জন্য ডিফল্ট সরলীকরণ মাত্রা/চিহ্নের পরিসর সম্পর্কে কোনো অনুমান করতে পারে না। অতএব, এটি দক্ষতার সাথে mod এবং div দিয়ে অভিব্যক্তিকে সরল করতে পারে না।

আমরা অ্যাফাইন ম্যাপে সাব-অভিব্যক্তির নিম্ন এবং উপরের সীমা সম্পর্কে জ্ঞান লাভ করতে পারি যাতে তাদের আরও সহজ করা যায়।

সরলীকরণকারী নিম্নলিখিত অভিব্যক্তিগুলি পুনরায় লিখতে পারে।

1. (d0, d1) -> (d0 + d1 floordiv 16, d1 mod 16) d- এর জন্য [0, 6] x [0, 14] হয়ে যায় (d0, d1) -> (d0, d1)
2. (d0, d1, d2) -> ((100d0 + 10d1 + d2) floorDiv 100, ((100d0 + 10d1 + d2) mod 100) floordiv 10, d2 mod 10) di in [0, 9] এর জন্য floordiv 10, d2 mod 10) হয়ে যায় (d0, d1, d2) -> (d0, d1, d2) ।
3. (d0, d1, d2) -> ((16d0 + 4d1 + d2) floordiv 8, (16d0 + 4d1 + d2) mod 8) d_i in [0, 9] হয়ে যায় (d0, d1, d2) -> (2d0 + (4d1 + d2) floordiv 8,(4d1 + d2) mod 8) ।
4. (d0, d1) -> (-(-11d0 - d1 + 109) floordiv 11 + 9) d এর জন্য [0, 9] x [0, 10] হয়ে যায় (d0, d1) -> (d0) ।

ইন্ডেক্সিং ম্যাপ সিম্পলিফায়ার আমাদের বুঝতে দেয় যে HLO-তে কিছু চেইন্ড রিশেপ একে অপরকে বাতিল করে।

p0 = f32[10, 10, 10] parameter(0)
reshape1 = f32[50, 20] reshape(p0)
reshape2 = f32[10, 10, 10] reshape(reshape1)

ইনডেক্সিং ম্যাপ এবং তাদের সরলীকরণের পরে আমরা পাব

(d0, d1, d2) -> (d0, d1, d2) ।

ইন্ডেক্সিং মানচিত্র সরলীকরণ সীমাবদ্ধতাগুলিকেও সরল করে।

1. lower_bound <= affine_expr (floordiv, +, -, *) constant <= upper_bound প্রকারের সীমাবদ্ধতা updated_lower_bound <= affine_expr <= updated_upped_bound হিসাবে পুনরায় লেখা হয়।
2. যে সীমাবদ্ধতাগুলি সর্বদা সন্তুষ্ট থাকে, যেমন d0 + s0 in [0, 20] এর জন্য d0 in [0, 5] এবং s0 in [1, 3] বাদ দেওয়া হয়।
3. সীমাবদ্ধতার মধ্যে Affine এক্সপ্রেশনগুলি উপরের সূচীকৃত affine মানচিত্র হিসাবে অপ্টিমাইজ করা হয়েছে।

আরও উদাহরণের জন্য indexing_map_test.cc দেখুন।