An Approach to Tight I/O Lower Bounds for Algorithms with Composite Procedures
摘要
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.