主要观点：时间复杂度模型在并行计算中存在缺陷，应使用工作深度模型来分析并行算法的复杂度。通过多个案例，如元素级乘法、向量求和、张量积、矩阵乘法、softmax 和注意力机制等，展示了不同算法在工作深度模型下的复杂度分析，强调注意力机制的渐近深度复杂度为 O(logn + logd)。同时指出深度分析存在局限性，如树的最大宽度大于计算单元、内存访问模式不连续或不可向量化、物化变量与内存层次结构不兼容等，在实际中需保证物化张量大小在 L2 缓存内。对于当前和未来芯片，若训练范式保持非并发，可通过将权重移至更快内存来改善计算。
关键信息：

• 2025 年多数计算机为多核，时间复杂度难以准确衡量算法快慢。
• 工作深度模型以计算图深度衡量算法复杂度，不受核心数量影响。
• 各案例中不同算法在工作深度模型下的具体操作及复杂度分析。
• 深度分析的局限性及在实际中需注意的内存相关问题。
• 注意力机制复杂度受物化张量大小影响，实际复杂度可能为 O(n log n)。
• 推测未来芯片可通过将权重移至更快内存改善计算。
  重要细节：
• 元素级乘法在计算图中各步骤独立，可并行处理，实际复杂度近似常数。
• 向量求和可通过成对操作并行化，渐近复杂度为 O(log n)。
• 张量积在张量大小适合缓存时深度为常数，不适合时变为顺序操作。
• 矩阵乘法是张量积与收缩的组合，渐近复杂度为 O(log n)。
• softmax 由多个元素级操作组成，渐近复杂度为 O(log n)。
• 注意力机制由多个矩阵乘法、收缩和元素级操作组成，渐近复杂度为 O(logn + logd)。
• 深度分析的局限性包括树宽度、内存访问模式和物化变量与内存层次结构等方面。
• 推测未来芯片可将权重移至 L2 等更快内存以改善计算。