Analyzing the I/O lower bound is crucial for enhancing dataflow performance within the memory hierarchy. Existing methods struggle with composite step programs, often underestimating I/O behavior during subcomputations. To address this, we introduce the \((X_1, X_2)\) -Partition theory, providing tighter I/O lower bounds for statically analyzable programs. We evaluate this theory on stencil operators and show that the I/O lower bound becomes tighter compared to X-Partition theory. Furthermore, we develop a method for calculating I/O lower bounds for composite algorithms using the \((X_1, X_2)\) -Partition theory. By analyzing the dataflow of the QR Decomposition algorithm, we demonstrate the effectiveness of our method in handling composite procedures. We also introduced this theory into the neural network architecture search task for the first time, and preliminary experimental results further demonstrated the broad application prospects of this theory.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Approach to Tight I/O Lower Bounds for Algorithms with Composite Procedures

  • Rui Xia,
  • Ligang Cao,
  • Huajian Zhang,
  • Jihu Guo,
  • Xiaowei Guo,
  • Jie Liu,
  • Huaimin Wang

摘要

Analyzing the I/O lower bound is crucial for enhancing dataflow performance within the memory hierarchy. Existing methods struggle with composite step programs, often underestimating I/O behavior during subcomputations. To address this, we introduce the \((X_1, X_2)\) -Partition theory, providing tighter I/O lower bounds for statically analyzable programs. We evaluate this theory on stencil operators and show that the I/O lower bound becomes tighter compared to X-Partition theory. Furthermore, we develop a method for calculating I/O lower bounds for composite algorithms using the \((X_1, X_2)\) -Partition theory. By analyzing the dataflow of the QR Decomposition algorithm, we demonstrate the effectiveness of our method in handling composite procedures. We also introduced this theory into the neural network architecture search task for the first time, and preliminary experimental results further demonstrated the broad application prospects of this theory.