Strassen矩阵乘法的通信成本| 2014年2月</t我tle> <link href="//www.eqigeno.com/stylesheets/all.css" rel="stylesheet"> <link href="//www.eqigeno.com/stylesheets/jplayer.pink.flag.css" rel="stylesheet"> <link href="//www.eqigeno.com/stylesheets/sections/videos.css" rel="stylesheet"> <link href="//www.eqigeno.com/stylesheets/tipsy.css" rel="stylesheet"> <link href="//www.eqigeno.com/stylesheets/colorbox.css" rel="stylesheet"> <style> html{overflow: auto !important;} </style> <style> iframe body { overflow: hidden; } iframe { border: none; margin: 0; } .fav_hacker_news { background:url('https://img.icons8.com/color/48/000000/hacker-news.png') no-repeat center #FFF; background-size: 21.5px; } .fav_hacker_news:hover { background:url('https://img.icons8.com/color/48/000000/hacker-news.png') no-repeat center #e6e9ea; background-size: 21.5px; } .fav_bar a.fav_reddit { background-size: 22px; background:url('//www.eqigeno.com/images/icons/reddit.gif') no-repeat center #FFF; } .fav_bar a.fav_reddit:hover { background-color: #e6e9ea; } .fav_bar a.fav_facebook { background-size: 22px; background:url('//www.eqigeno.com/images/icons/facebook.gif') no-repeat center #FFF; } .fav_bar a.fav_facebook:hover { background-color: #e6e9ea; background:url('//www.eqigeno.com/images/icons/facebook.gif') no-repeat center #e6e9ea; } body { margin: 0 } #acmWidget.resourcesWidget .dateNews { margin-left: 10px; } </style> </head> <body id="body-main" itemscope itemtype="http://schema.org/Article"> <div id="domain-info" data-domain="www.eqigeno.com"></div> <div class="JumpLink" id="PageTop"></div> <div id="container"> <div id="layout"> <header class="topHeader"> <a href="//www.eqigeno.com/" title="ACM" id="topLogo">ACM</a> <div id="instName"> <img src="//www.eqigeno.com/images/icons/acm_header.png" height="40" width="40" class="logo-mini" alt="acm-header"> </div> <a href="//www.eqigeno.com/login" title="登录" id="topSignIn">登录</a> <div id="topForm"> <form action="/search" method="get"> <div class="portaInput"> <label for="searchInput" id="labelSearchInput" class="inField"></label> <input type="text" id="searchInput" class="st-default-search-input" placeholder="Search" name="q" aria-label="Search"> </div> <button name="search submit" type="submit" id="searchSubmit">去</button> </form> </div> <div id="topBar"> <ul> <li><a href="https://www.acm.org/" title="ACM.org">ACM.org</a></li> <li><a href="https://campus.acm.org/public/qj/brandingqj/cacm.cfm" target="_blank" title="加入ACM">加入ACM</a></li> <li><a href="//www.eqigeno.com/about-communications" title="vwin德赢AC米兰官网网址">vwin德赢AC米兰官网网址</a></li> <li><a href="//www.eqigeno.com/acm-resources" title="vwin德赢网页版">vwin德赢网页版</a></li> <li class="last-child"><a href="//www.eqigeno.com/alerts-and-feeds" title="警报&提要">警报&提要</a></li> <li class="last-child"><a href="https://www.facebook.com/Communications-of-the-ACM-521319564596131/" style="margin: 0;padding: 0;margin-right: 1px;margin-top: -2px;"><img src="//www.eqigeno.com/images/icons/facebook.png" alt="脸谱网" style="height: 18px;width: 18px;"></a><a href="https://twitter.com/cacmmag" style="margin: 0;padding: 0;margin-top: -1px;margin-right: 4px;"><img src="//www.eqigeno.com/images/icons/twitter.png" alt="推特" style="width: 16px;height: 16px;"></a><a href="//www.eqigeno.com/alerts-and-feeds/rss-feeds" style="margin: 0;padding: 0;"><img src="//www.eqigeno.com/images/icons/rss.png" alt="rss" style="width: 14px;height: 14px;"></a></li> </ul> </div> <hgroup> <h1><a href="//www.eqigeno.com/" title="ACM通信">ACM通信</a></h1> </hgroup> <nav> <ul> <li class="first-child"><a href="//www.eqigeno.com/" class="menuText itemHome">首页</a></li> <li> <div class="portaDropdown"> <a class="withMenu menuText itemCurrent" href="//www.eqigeno.com/magazines/2022/7">vwin德赢AC米兰官网网址</a> <div class="menuLinks currenIssueDropdown"> <a class="menuCover" href="//www.eqigeno.com/magazines/2022/7"><img src="//www.eqigeno.com/system/assets/0004/3300/July2022-Cover.1000x1338.large.jpg?1655386841&1655386840" width="145" height="192" alt="最新一期"></a> <span class="dropDownIssueTitle">vwin德赢AC米兰官网网址本期:2022年7月</年代pan> <a href="//www.eqigeno.com/magazines/2022/7/262079-toward-verified-artificial-intelligence">走向可验证的人工智能</a> <a href="//www.eqigeno.com/magazines/2022/7/262082-expressive-querying-for-accelerating-visual-analytics">用于加速视觉分析的表达查询</a> <a href="//www.eqigeno.com/magazines/2022/7/262084-cacm-community"><i>CACM</我>社区</a> <a class="lastLink" href="//www.eqigeno.com/magazines/2022/7">查看目录</a> </div> </div></li> <li> <div class="portaDropdown"> <a href="//www.eqigeno.com/news" class="withMenu menuText itemNews">新闻</a> <div class="menuLinks newsDropdown"> <a href="//www.eqigeno.com/news" class="lastLink">最新消息</a> <a href="//www.eqigeno.com/news/archive" class="lastLink">新闻存档</a> </div> </div></li> <li> <div class="portaDropdown"> <a href="//www.eqigeno.com/blogs/about-the-blogs" class="withMenu menuText itemBlogs">vwin德赢AC米兰官网网址 </a> <div class="menuLinks blogsDropdown"> <a href="//www.eqigeno.com/blogs/about-the-blogs">vwin德赢AC米兰官网网址 </a> <a href="//www.eqigeno.com/blogs/blog-cacm">vwin德赢AC米兰官方 </a> <a href="//www.eqigeno.com/blogs/blogroll">vwin德赢ac米兰合作 </a> <a href="//www.eqigeno.com/blogs/archive" class="lastLink">博客档案</a> </div> </div></li> <li> <div class="portaDropdown"> <a href="//www.eqigeno.com/opinion" class="withMenu menuText itemOpinion">的意见</a> <div class="menuLinks opinionDropdown"> <a href="//www.eqigeno.com/opinion/articles">文章</a> <a href="//www.eqigeno.com/opinion/interviews">面试</a> <a href="//www.eqigeno.com/opinion/archive" class="lastLink">意见归档</a> </div> </div></li> <li> <div class="portaDropdown"> <a href="//www.eqigeno.com/research" class="withMenu menuText itemResearch">研究</a> <div class="menuLinks researchDropdown"> <a href="//www.eqigeno.com/research">最新的研究</a> <a href="//www.eqigeno.com/research/archive" class="lastLink">vwin668 </a> </div> </div></li> <li> <div class="portaDropdown"> <a href="//www.eqigeno.com/practice" class="withMenu menuText itemPractice">实践</a> <div class="menuLinks practiceDropdown"> <a href="//www.eqigeno.com/practice">最新的实践</a> <a href="//www.eqigeno.com/practice/archive" class="lastLink">实践存档</a> </div> </div></li> <li> <div id="careersNav" class="portaDropdown"> <a href="//www.eqigeno.com/careers" class="withMenu menuText itemOpinion">vwin德赢ac米兰官网 </a> <div class="menuLinks opinionDropdown"> <ul> <li><a href="http://jobs.acm.org/jobs/search/results?rows=15&radius=0&view=List_Detail&sort=score+desc" target="_blank">找工作</a></li> <li><a href="http://jobs.acm.org/jobs/resumes/create" target="_blank">发布一个简历</a></li> <li><a href="http://jobs.acm.org/jobs/products" target="_blank">发布一个职位</a></li> <li><a href="https://www.acm.org/publications/advertising" target="_blank">广告与我们</a></li> <li class="lastLink"><a href="mailto:careers@acm.org">联系我们</a></li> </ul> </div> </div></li> <li> <div class="portaDropdown"> <a href="//www.eqigeno.com/magazines" class="withMenu menuText itemPrevious on">存档</a> <div class="menuLinks previousDropdown"> <span class="previousIssueTitle">杂志档案库收录了刊登在<我>ACM通信</我>在过去的50年里。</年代pan> <div class="issue"> <a href="//www.eqigeno.com/magazines/2022/7">2022年7月(第65卷第7期)</a> </div> <div class="issue"> <a href="//www.eqigeno.com/magazines/2022/6">2022年6月(第65卷第6期)</a> </div> <div class="issue"> <a href="//www.eqigeno.com/magazines/2022/5">2022年5月(第65卷第5期)</a> </div> <a href="//www.eqigeno.com/magazines" class="lastLink">查看更多问题</a> </div> </div></li> <li><a href="//www.eqigeno.com/videos" class="menuText itemVideos">视频</a></li> </ul> </nav> </header> <section> <div class="breadcrum"> <a href="//www.eqigeno.com/">首页</a> <span>/</年代pan> <a href="//www.eqigeno.com/magazines/decade">杂志存档</a> <span>/</年代pan> <a href="//www.eqigeno.com/magazines/2014/2">2014年2月(第57卷第2期)</a> <span>/</年代pan> <a href="//www.eqigeno.com/magazines/2014/2/171673-communication-costs-of-strassens-matrix-multiplication">斯特拉森矩阵乘法的通信代价</a> <span>/</年代pan>全文</d我v> <div class="col0 floatLeft firstCol"> <span class="label">研究突出了</年代pan> <h2>斯特拉森矩阵乘法的通信代价</h2> <h6 class="subheader"></h6> </div> <hr class="dotted"> <div id="articleFullText" class="col1 floatLeft firstCol"> <span class="byline">作者:格雷·巴拉德，詹姆斯·德梅尔，奥尔加·霍尔兹，奥德·施瓦茨<br>ACM通讯，2014年2月，Vol. 57 No. 2, 107-114页<br>10.1145/2556647.2556660<br><a href="#comments">评论</a></span> <div class="fav_bar"> <span>认为:</年代pan> <a href="#" onclick="javascript:window.print();" class="fav_print" title="打印">打印</a> <a href="//www.eqigeno.com/about-communications/mobile-apps/" class="mobile-apps" title="手机应用程序">手机应用程序</a> <a href="https://dl.acm.org/citation.cfm?id=2556647.2556660&coll=portal&dl=ACM" class="fav_acm_digital" target="_blank" title="ACM数字图书馆">ACM数字图书馆</a> <a href="//www.eqigeno.com/magazines/2014/2/171673-communication-costs-of-strassens-matrix-multiplication/pdf" class="fav_pdf" rel="nofollow" target="_blank" title="全文(PDF)">全文(PDF)</a> <a href="https://dl.acm.org/ft_gateway.cfm?id=2556660&ftid=1426443&dwn=1" class="fav_de" target="_blank" title="数码版">数码版</a> <span>分享:</年代pan> <a href="javascript:void(0);" class="fav_email" title="通过电子邮件发送" id="sendByEmail">通过电子邮件发送</a> <a href="javascript:void(0);" class="fav_reddit" onclick="addthis_sendto('reddit');" title="在reddit分享">在reddit分享</a> <a href="javascript:void(0);" class="fav_su" onclick="addthis_sendto('stumbleupon');" title="在StumbleUpon分享">在StumbleUpon分享</a> <a href="https://news.ycombinator.com/" class="fav_hacker_news" title="分享到黑客新闻">分享到黑客新闻</a> <a href="javascript:void(0);" class="fav_twitter" onclick="addthis_sendto('twitter');" title="在推特上分享">在推特上分享</a> <a href="javascript:void(0);" class="fav_facebook" onclick="addthis_sendto('facebook');" title="在Facebook上分享">在Facebook上分享</a> <div class="addthis_toolbox "> <a href="https://www.addthis.com/bookmark.php?v=250&pubid=xa-4dcbeff2515fc93c" class="addthis_button_compact fav_more no_border">分享</a> </div> </div> <div class="clearer"></div> <div class="imageWithCaptionLeft" id="asset-14502"> <figure> <img alt="数值矩阵" src="//www.eqigeno.com/system/assets/0001/4502/012114_Survivalist_Communication-Costs2.large.jpg?1476779463&1390327926" title="numerical matrix"> <figcaption> <p class="credit">来源:Survivalist.com</p> </figcaption> </figure> </div> <a name="body-1"></a> <p>历史上，算法的评估依据是它们执行的算术运算的数量。这种分析不再足以预测今天机器上的运行时间。在内存层次和处理器之间移动数据比执行计算需要更多的时间(和能量)。硬件趋势表明，这种通信的相对成本只会增加。因此，证明算法通信的下界和找到达到这些边界的算法是基本目标。我们证明了算法的通信代价与其相应计算图的图展开性质密切相关。</p> <p>矩阵乘法是科学计算和并行计算中最基本的问题之一。将展开分析应用于Strassen等快速矩阵乘法算法，得到了它们通信代价的第一个下界。这些边界表明，当前的顺序算法是最优的，但以前的并行算法通信过多。我们新的并行化的Strassen的算法是通信最优和优于所有以前的矩阵乘法算法。</p> <p class="totop"><a href="#PageTop">回到顶部</a></p> <a name="body-2"></a> <h3>1.简介</h3.．> <p>通信(即移动数据)可以在很大程度上支配算法的代价，无论代价是以运行时间还是总能量来衡量的。这适用于在内存层次之间或通过网络在处理器之间移动数据。每个数据单元的通信时间变化数量级，从10数量级不等<年代up>9</年代up>L1缓存引用的顺序为10秒<年代up>2</年代up>磁盘访问的秒数。当交流发生在网络或互联网上时，变化可能更大。事实上，技术趋势<年代up><a href="#R16">16</a>，<a href="#R17">17</a></sup>与算术成本相比，通信成本随着时间的推移呈指数增长。摩尔定律使芯片运算能力每年提高约60%，但内存和网络带宽每年仅提高26%和23%。<年代up><a href="#R16">16</a></sup>因此，即使在今天沟通不是瓶颈的情况下，未来也可能是。</p> <p>理想情况下，我们将能够确定重要问题所需通信量的下界，并设计实现这些问题的算法，即通信最优的算法。长期以来，这些双重问题一直吸引着研究人员，其中一个典型的例子是(<我>n</我><sup><a href="#R3">3.</a></sup>)矩阵乘法(详见下文)，并在Hong和Kung中证明了下界<年代up><a href="#R18">18</a></sup>和Irony等人。<年代up><a href="#R20">20.</a></sup>和许多最优的顺序和并行算法，如Agarwal等。<年代up><a href="#R1">1</a></sup>和大炮<年代up><a href="#R11">11</a></sup>．</p> <p>最近，这些下界已经扩展到一大类其他经典线性代数问题，包括线性系统求解、最小二乘和特征值问题、密集和稀疏矩阵、顺序和并行机器。<年代up><a href="#R9">9</a></sup>令人惊讶的是，在LAPACK和ScaLAPACK等广泛实现的库中，高度优化的算法<年代up><a href="#R3">3.</a></sup>即使在渐近意义上，通常也达不到这些下界。这导致了很多最近的工作，发明了新的、更快的算法;参见巴拉德等人的引文。<年代up><a href="#R9">9</a>，<a href="#R10">10</a></sup>为引用。</p> <p>在本文中，我们描述了一种新的方法来证明Strassen (<我米g src="https://dl.acm.org/cms/attachment/905dcba9-ff1d-4011-b0bc-b3427a05b7bf/cacm5702_i.gif" border="0" hspace="2" alt="cacm5702_i.gif">)矩阵乘法算法，以及许多类似的快速算法。具体地，我们介绍了算法的计算图的展开分析，并表明这种展开有助于确定通信成本。这些通信成本界限是<我>较低的</我>这意味着Strassen的算法不仅减少了计算量，而且为减少通信创造了机会。此外，下界随着可用内存的增加而减少，这表明使用额外的内存也可能允许更快的算法。</p> <p>事实上，有一种最优的并行算法可以在不同的内存数量下达到我们的下界，它的性能超过了所有其他已知的矩阵乘法实现，经典的或基于strassen的，在一个大型并行机器上，<年代up><a href="#R6">6</a></sup>看到<a href="#F1">图1</a>．在本文的其余部分，我们重点解释我们的新的下界Strassen的算法和他们的含义。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>1.1.通信模型</b></p> <p>为了分析算法的通信代价，我们考虑了理想化的内存模型和通信模型。在连续的情况下(参见<a href="#F2">图2</a>)时，我们认为机器具有两层内存层次:快速内存大小<我>米</我>字(在这里执行计算)和无限大的缓慢内存。我们假设输入最初驻留在慢速内存中，并且由于太大而无法容纳在快速内存中。我们定义的<我>沟通成本</我>序列算法的总字数为在慢速存储器和快速存储器之间传输的字数。</p> <p>在平行情况下(参见<a href="#F2">图2</a>),我们认为<我>p</我>处理器，每个处理器都有一定大小的本地内存<我>米</我>，通过网络连接。在这种情况下，通信成本是处理器之间传输的字数，沿着算法的关键路径计算。也就是说，在不同的处理器对之间同时通信的两个字只计算一次。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>1.2.经典的矩阵乘法</b></p> <p>为了说明算术重排序对序列计算的通信和运行时间的影响，考虑矩阵乘法的计算问题<我>C</我>＝<我>一个</我>·<我>B</我>，其中(<我>我,我</我>）<年代up>th</年代up>输出元件由经典公式计算<我>C</我><sub><i>ij</我></sub>＝<年代ub>k</年代ub><i>一个</我><sub><i>本土知识</我></sub>·<我>B</我><sub><i>kj</我></sub>．经典算法的一种“朴素”的计算顺序可以简单地通过三个嵌套循环来指定(参见算法1)。对于过大而无法在快速内存中容纳的矩阵，这种排序需要对每个标量乘法至少通信一个操作数，导致总通信成本为(<我>n</我><sup><a href="#R3">3.</a></sup>)．一个很自然的问题是:我们能做得更好吗?</p> <p><img src="https://dl.acm.org/cms/attachment/8bb76c26-0d36-48d5-9153-438f1438e0e5/ins01.gif" border="0" hspace="5" vspace="5" alt="ins01.gif"></p> <p>答案是肯定的。我们可以通过使用“阻塞”算法(参见算法2)来减少通信<我>A、B</我>,<我>C</我>分成正方形大小的方块<我>b</我>×<我>b</我>这样三个块就可以同时放入快速存储器中。我们用这个符号<我>C</我>［<我>我,我</我>]来参考(<我>我,我</我>）<年代up>th</年代up><i>b</我>×<我>b</我>块的<我>C</我>矩阵。当<我>C</我>［<我>我,我</我>),<我>一个</我>［<我>我,K</我>),而<我>B</我>［<我>J K,</我>都在快速内存中，那么算法的内部循环(对应于(<我>b</我><sup>3.</年代up>(算术运算)可以在没有更多通信的情况下执行。</p> <p><img src="https://dl.acm.org/cms/attachment/cbfaa2ec-54f0-4e76-8123-7c5a79d13e04/ins02.gif" border="0" hspace="5" vspace="5" alt="ins02.gif"></p> <p>的最大块大小<我>b</我>＝<我米g src="https://dl.acm.org/cms/attachment/fdbc668e-562d-4a92-a393-9d1a29960b73/cacm5702_j.gif" border="0" hspace="2" alt="cacm5702_j.gif">，则结果为((<我>n</我>/<我米g src="https://dl.acm.org/cms/attachment/70492289-a7d0-4193-a1ca-efe9aafb8fcc/cacm5702_k.gif" border="0" hspace="2" alt="cacm5702_k.gif">）<年代up>3.</年代up>)块操作，每个操作需要(<我>米</我>)要交流的词语。因此，总通信成本为(<我>n</我><sup>3.</年代up>/<我米g src="https://dl.acm.org/cms/attachment/70492289-a7d0-4193-a1ca-efe9aafb8fcc/cacm5702_k.gif" border="0" hspace="2" alt="cacm5702_k.gif">)，因子为(<我>米</我>)优于朴素算法。</p> <p>在顺序机器上，朴素算法和阻塞算法之间的典型性能差异是一个数量级。采用分块算法，得到的性能接近机器的峰值性能。问题又来了:我们能做得更好吗?我们能否进一步重新排序这些计算以减少通信?</p> <p>如果我们坚持执行(<我>n</我><sup>3.</年代up>根据经典公式给出的算术运算，答案是否定的。洪教授和龚<年代up><a href="#R18">18</a></sup>证明了通信成本下界为(<我>n</我><sup>3.</年代up>/<我米g src="https://dl.acm.org/cms/attachment/70492289-a7d0-4193-a1ca-efe9aafb8fcc/cacm5702_k.gif" border="0" hspace="2" alt="cacm5702_k.gif">)，表明阻塞算法是通信最优的。但这并不是故事的结束:阻塞算法的通信最优性假设(<我>n</我><sup>3.</年代up>算术运算。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>1.3.Strassen矩阵乘法</b></p> <p>虽然矩阵乘法的经典算法已经被优化，以尽可能减少通信成本，一个完全不同的算法方法来解决这个问题是可能的。让我们回顾一下Strassen的算法<年代up><a href="#R24">24</a></sup>(参见算法3)。</p> <p>Strassen的关键思想是用7个标量乘而不是8个矩阵来乘2 × 2矩阵。因为<我>n</我>×<我>n</我>矩阵可以分为象限，Strassen的想法递归地应用。七象限的每一个乘法都是递归计算的，象限的加减法的计算成本为(<我>n</我><sup>2</年代up>)．因此，触发器计数的递归式为<我>F</我>（<我>n</我>) = 7<我>F</我>（<我>n</我>/ 2) + (<我>n</我><sup>2</年代up>)与基本情况<我>F</我>(1) = 1，得到<我>F</我>（<我>n</我>) = (<我米g src="https://dl.acm.org/cms/attachment/905dcba9-ff1d-4011-b0bc-b3427a05b7bf/cacm5702_i.gif" border="0" hspace="2" alt="cacm5702_i.gif">)，其计算量渐近小于经典算法。</p> <p>下面一节给出的主要结果揭示了一个奇妙的事实:Strassen的算法不仅比经典算法需要更少的计算，而且它需要更少的通信!</p> <p><img src="https://dl.acm.org/cms/attachment/6c24cb05-165b-4596-abec-21699eb1c282/ins03.gif" border="0" hspace="5" vspace="5" alt="ins03.gif"></p> <p class="totop"><a href="#PageTop">回到顶部</a></p> <a name="body-3"></a> <h3>2.沟通下界</h3.．> <p>在这一节中，我们陈述了我们的主要结果:Strassen矩阵乘法的通信下界。第3节中描述的证明技术允许我们在顺序和并行的情况下声明边界。正如在第1节中提到的，下界比经典算法的下界要低。<年代up><a href="#R18">18</a>，<a href="#R20">20.</a></sup>在顺序和并行的情况下，现在都存在达到下界的通信最优算法。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>2.1.连续的情况下</b></p> <p>得到下界如下:</p> <p>定理1。<年代up><a href="#R10">10</a></sup><i>考虑Strassen的算法在一个内存大小为M的顺序机器上实现，那么对于mn</我><sup>2</年代up>，<我>Strassen算法的通信代价为</我></p> <p align="center"><img src="https://dl.acm.org/cms/attachment/dd12748e-edc2-456c-b406-d844b49de446/ueq01.gif" border="0" hspace="2" vspace="5" alt="ueq01.gif"></p> <p>它适用于任何实现和任何已知的Strassen算法变体，该算法是基于执行2 × 2矩阵乘法和7个标量乘法。这包括Winograd的<我>O</我>（<我米g src="https://dl.acm.org/cms/attachment/905dcba9-ff1d-4011-b0bc-b3427a05b7bf/cacm5702_i.gif" border="0" hspace="2" alt="cacm5702_i.gif">)变体使用15次加法而不是18次，这是实践中最常用的快速矩阵乘法算法。</p> <p>这个下界是紧的，因为它是通过标准的递归顺序实现Strassen的算法。通过递归式给出了递归算法的通信代价<我米g src="https://dl.acm.org/cms/attachment/4461f8d4-d6ca-492a-ad45-e57d4f92a84e/cacm5702_l.gif" border="0" hspace="2" alt="cacm5702_l.gif">．当输入和输出子矩阵适合快速存储器并且矩阵乘法可以在没有进一步通信的情况下执行时，就会发生基本情况。这个收益率</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/4e066d7e-39d1-4e15-bf46-69bd896835b2/ueq02.gif" border="0" hspace="2" vspace="5" alt="ueq02.gif"></p> <p>为<我>mn</我><sup>2</年代up>，与定理1中的下界相匹配。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>2.2.平行的情况下</b></p> <p>定理1的证明技术可以推广到并行机器，从而得到</p> <p>推论2。<年代up><a href="#R10">10</a></sup><i>考虑Strassen的算法在一个有p个处理器的并行机器上实现，每个处理器的本地内存大小为m<我米g src="https://dl.acm.org/cms/attachment/ef43cfb5-7e65-4f86-afbb-450ef60000aa/cacm5702_m.gif" border="0" hspace="2" alt="cacm5702_m.gif">， Strassen算法的通信代价为</我></p> <p align="center"><img src="https://dl.acm.org/cms/attachment/6c3e2489-7743-4751-9281-03d6e4581fa1/ueq03.gif" border="0" hspace="2" vspace="5" alt="ueq03.gif"></p> <p>虽然推论2并不适用于所有大小的本地内存(相对于问题的大小和处理器的数量)，但可以使用类似的技术证明以下与内存无关的下界<年代up><a href="#R5">5</a></sup>并且适用于所有本地内存大小，尽管它需要单独的假设。</p> <p>定理3。<年代up><a href="#R5">5</a></sup><i>假设一个并行算法执行Strassen矩阵乘法负载平衡计算。则通信成本为</我></p> <p align="center"><img src="https://dl.acm.org/cms/attachment/5292c27f-06d8-443d-a48a-41bccd8cf939/ueq04.gif" border="0" hspace="2" vspace="5" alt="ueq04.gif"></p> <p>注意推论2中的界优于定理3中的界<我>米</我>＝<我>O</我>（<我>n</我><sup>2</年代up>/<我>p</我><sup>2 /日志7</年代up>)．因此，并行实现Strassen的最紧下界就是这两个边界的最大值。<a href="#T2">表2</a>而且<a href="#F3">图3</a>，都改编自Ballard等人，<年代up><a href="#R5">5</a></sup>说明两个函数之间的关系。<a href="#F3">图3</a>特别地，它显示了固定维度的强缩放边界<我>n</我>，增加处理器的数量(每个处理器都有本地内存大小)<我>米</我>)并不会增加通讯总量。因此，关键路径上的通信成本随时间线性降低<我>p</我>．这是因为在这个“完美强缩放范围”中，主导下界包括一个<我>p</我>分母;然而，当第二个界限开始占主导地位时，分母包含a<我>p</我><sup>2／3</年代up>而不是<我>p</我>,并增加<我>p</我>导致更多的沟通量。如图所示，经典算法也出现了类似的现象，只是参数略有不同。<年代up><a href="#R5">5</a>，<a href="#R23">23</a></sup></p> <p>斯特拉森矩阵乘法的最新并行算法<年代up><a href="#R6">6</a></sup>沟通成本</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/3176dda3-de2e-453e-b665-11246aee1b97/ueq05.gif" border="0" hspace="2" vspace="5" alt="ueq05.gif"></p> <p>在哪里<我>p</我>是处理器的数量和<我>米</我>是本地内存的大小。注意，这与上面的推论2和定理3的下界相匹配。McColl和Tiskin给出了BSP模型中Strassen矩阵乘法的类似算法。<年代up><a href="#R22">22</a></sup></p> <p class="totop"><a href="#PageTop">回到顶部</a></p> <a name="body-4"></a> <h3>3.证明了</h3.．> <p>定理1证明的关键是估计Strassen算法计算图的边展开。下面我们将描述通信成本是如何与这个图的边展开特性密切相关的。图具有递归结构，我们用组合分析的方法展开。高级的参数是基于分段计算的，我们将在3.3节中解释。让我们首先定义两个关键概念:计算图和边展开。参见Ballard等人。<年代up><a href="#R10">10</a></sup>为了充分的证据。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>3.1.计算图</b></p> <p>算法对给定输入所执行的计算可以建模为计算有向无环图(<我>CDAG</我>):我们为每个输入、中间和输出参数设置了一个顶点，并根据直接依赖关系(例如，对于二进制算术操作)设置了边<我>x</我>: =<我>y + z</我>，我们有与操作数对应的顶点的有向边<我>y</我>而且<我>z</我>对应的顶点<我>x</我>)．</p> <p>在顺序的情况下，实现(或调度)决定算术操作的执行顺序，这与CDAG的部分顺序有关。在并行情况下，实现决定哪些算术运算由哪个<我>p</我>以及处理器对本地操作的排序。这对应于将CDAG划分为<我>p</我>部分。各个部分之间的边交叉对应的是一个处理器拥有但另一个处理器需要的参数，因此与通信有关。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>3.2.边缘扩张</b></p> <p>展开是一个图论概念<年代up><a href="#R19">19</a></sup>它将图的一个给定子集与其边界联系起来。如果一个图有较大的展开，那么顶点的子集就会有较大的边界。例如，每个顶点都有北、南、东、西邻居的2D网格的扩展较小，而一个完整的图的扩展较大。虽然扩展度量有几种变体，但我们感兴趣的是正则图的边展开，定义如下:边展开<我>h</我>（<我>G</我>)<我>d</我>常规的无向图<我>G</我>= (<我>V E</我>)是</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/12a49004-0daf-490d-ac21-6291155e9317/eq01.gif" border="0" hspace="2" vspace="5" alt="eq01.gif"></p> <p>在哪里<我>E</我><sub><i>G</我></sub>（<我>A、B</我>)是连接不相交顶点集的边的集合<我>一个</我>而且<我>B</我>．</p> <p>注意，cdag通常是不规律的。如果一个图<我>G</我>= (<我>V E</我>)不是规则的，但有一个有界的极大度<我>d</我>，然后添加(<<我>d</我>)循环到度<的顶点<我>d</我>，得到正则图<我>G</我>．我们使用的惯例是，一个循环将顶点的度数加1。注意，对于任何<我>年代</我><i>V</我>我们有|<我>E</我><sub><i>G</我></sub>（<我>年代,V \ S</我>)|<我>= | E</我><sub><i>G</我></sub>（<我>年代,V</我>(S)|，因为添加的循环中没有一个对的边缘扩展有贡献<我>G</我>．</p> <p>对于许多图，小集合比大集合具有更大的展开。让<我>h</我><sub><i>年代</我></sub>（<我>G</我>)表示的边展开<我>G</我>对于大小最多的集合<我>年代</我>：</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/e5f593a4-6b3f-4bc7-9d2f-f0a8a2e9d338/eq02.gif" border="0" hspace="2" vspace="5" alt="eq02.gif"></p> <p>对于许多有趣的图族(包括Strassen的CDAG)，<我>h</我><sub><i>年代</我></sub>（<我>G</我>)不依赖于|<我>V</我>（<我>G</我>) |<我>年代</我>是固定的，尽管它可能在什么时候下降<我>年代</我>增加。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>3.3.分区参数</b></p> <p>高级下界参数的基础是将算法实现的执行划分为多个段。让<我>O</我>是尊重CDAG的部分排序的顶点的任何总排序<我>G</我>，也就是说，所有边的总顺序都是向上的。这个总排序可以被认为是执行计算的实际顺序。让<我>P</我>是<我>V</我>成段<我>年代</我><sub>1</年代ub>，<我>年代</我><sub>2</年代ub>,……，这a segment<我>年代</我><sub><i>我</我></sub><i>P</我>在整个排序中是连续的顶点的子集吗<我>O</我>．</p> <p>让<我>年代</我>做一些线段，然后定义<我>R</我><sub><i>年代</我></sub>而且<我>W</我><sub><i>年代</我></sub>分别为读操作数和写操作数的集合(参见<a href="#F4">图4</a>),即<我>R</我><sub><i>年代</我></sub>顶点的集合在外面吗<我>年代</我>有一个边缘进入<我>年代</我>,<我>W</我><sub><i>年代</我></sub>顶点的集合在里面吗<我>年代</我>有一个边缘在外面<我>年代</我>．回想一下,<我>米</我>是快速内存的大小。然后，由于读取操作数而产生的总通信开销<我>年代</我>至少是|<我>R</我><sub><i>年代</我></sub><i>|米</我>最多<我>米</我>所需的|<我>R</我><sub><i>年代</我></sub>当段启动时，|操作数已经在快速内存中。同样的,<我>年代</我>导致至少|<我>W</我><sub><i>年代</我></sub>|<我>米</我>实际的写操作，最多<我>米</我>当这个段结束时，其他段需要的操作数会留在快速内存中。因此，总通信成本被限制在以下</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/bce5e36c-8297-4044-97ab-e984ee251c86/eq03.gif" border="0" hspace="2" vspace="5" alt="eq03.gif"></p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>3.4.边缘扩展和通信</b></p> <p>考虑一个段<我>年代</我>以及它的读写操作数<我>R</我><sub><i>年代</我></sub>而且<我>W</我><sub><i>年代</我></sub>(见<a href="#F4">图4</a>)．如果图<我>G</我>包含<我>年代</我>有<我>h</我>（<我>G</我>)边缘扩张，最大程度<我>d</我>至少2|<我>年代</我>的定义<我>h</我>（<我>G</我>)),我们有</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/ce1e181d-a6df-4286-b1ca-4df271e55608/ueq06.gif" border="0" hspace="2" vspace="5" alt="ueq06.gif"></p> <p>结合(3)，选择划分<我>V</我>成|<我>V</我>相同大小的|/s段<我>年代</我>,我们获得<我>IO</我>马克斯<年代ub><i>年代</我></sub>(|<我>V</我>| / s)·(<我>h</我>（<我>G</我>)·<我>年代</我>2<我>米</我>) = (|<我>V</我>| ?<我>h</我>（<我>G</我>))。在许多情况下,<我>h</我>（<我>G</我>)太小，无法达到期望的通信成本下限。通常情况下,<我>h</我>（<我>G</我>)是|的递减函数<我>V</我>（<我>G</我>) |;也就是说，随着相应算法的输入量和算术运算次数的增加(Strassen的算法就是这样)，边的展开会逐渐恶化。在这种情况下，最好考虑扩展<我>G</我>仅在小范围内:<我>IO</我>马克斯<年代ub><i>年代</我></sub>(|<我>V</我>|/<我>年代</我>)·(<我>h</我><sub><i>年代</我></sub>（<我>G</我>)·<我>年代</我>2<我>米</我>)．选择最小的<我>年代</我>这</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/e772dc75-096d-49f4-bfe1-97e2b21f2a75/eq04.gif" border="0" hspace="2" vspace="5" alt="eq04.gif"></p> <p>我们获得</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/3d93c156-ec06-47e7-a6e6-842b13f4c5bd/eq05.gif" border="0" hspace="2" vspace="5" alt="eq05.gif"></p> <p>值的存在<我>年代</我>|<我>V</我>满足条件(4)的|/2并不总是保证的。在巴拉德等人的研究中，<年代up><a href="#R10">10</a></sup>我们确认这个的存在<我>年代</我>对于足够大的|的Strassen的CDAG<我>V</我>|。</p> <p class="totop"><a href="#PageTop">回到顶部</a></p> <a name="body-5"></a> <h3>4.Strassen CDAG</h3.．> <p>回想一下矩阵乘法的Strassen算法，并考虑它的计算图。如果我们让<我>H</我><sub><i>我</我></sub>为Strassen深度递归算法的计算图<我>我</我>,然后<我>H</我><sub><img src="https://dl.acm.org/cms/attachment/b9205ed4-ddaa-425d-a4ed-83dbabe5f1a8/cacm5702_n.gif" border="0" hspace="2" alt="cacm5702_n.gif"></sub>对应于输入矩阵大小的计算<我>n</我>×<我>n</我>．让我们首先考虑<我>H</我><sub>1</年代ub>所示<a href="#F5">图5</a>，这对应于2 × 2矩阵的相乘。每个人<我>一个</我>而且<我>B</我>被“编码”为七对乘法输入，然后与乘法输出相对应的顶点被“解码”以计算输出矩阵<我>C</我>．</p> <p>通用计算图<我>H</我><sub><img src="https://dl.acm.org/cms/attachment/b9205ed4-ddaa-425d-a4ed-83dbabe5f1a8/cacm5702_n.gif" border="0" hspace="2" alt="cacm5702_n.gif"></sub>也有类似的结构:</p> <ul class="acm"> <li>编码<我>一个</我>:生成元素的加权和<我>一个</我></li> <li>编码<我>B</我>:生成元素的加权和<我>B</我></li> <li>的编码相乘<我>一个</我>而且<我>B</我>element-wise</li> <li>解码<我>C</我>:取乘积的加权和</li> </ul> <p>表示由<我>内附</我><sub><img src="https://dl.acm.org/cms/attachment/b9205ed4-ddaa-425d-a4ed-83dbabe5f1a8/cacm5702_n.gif" border="0" hspace="2" alt="cacm5702_n.gif"></sub><i>一个</我>的部分<我>H</我><sub><img src="https://dl.acm.org/cms/attachment/b9205ed4-ddaa-425d-a4ed-83dbabe5f1a8/cacm5702_n.gif" border="0" hspace="2" alt="cacm5702_n.gif"></sub>这对应于矩阵的编码<我>一个</我>．同样的,<我>内附</我><sub><img src="https://dl.acm.org/cms/attachment/b9205ed4-ddaa-425d-a4ed-83dbabe5f1a8/cacm5702_n.gif" border="0" hspace="2" alt="cacm5702_n.gif"></sub><i>B</我>,<我>12月</我><sub><img src="https://dl.acm.org/cms/attachment/b9205ed4-ddaa-425d-a4ed-83dbabe5f1a8/cacm5702_n.gif" border="0" hspace="2" alt="cacm5702_n.gif"></sub><i>C</我>对应的部分<我>H</我><sub><img src="https://dl.acm.org/cms/attachment/b9205ed4-ddaa-425d-a4ed-83dbabe5f1a8/cacm5702_n.gif" border="0" hspace="2" alt="cacm5702_n.gif"></sub>计算的编码<我>B</我>而解码<我>C</我>,分别。<a href="#F6">图6</a>展示了高水平的图片<我>H</我><sub><img src="https://dl.acm.org/cms/attachment/b9205ed4-ddaa-425d-a4ed-83dbabe5f1a8/cacm5702_n.gif" border="0" hspace="2" alt="cacm5702_n.gif"></sub>．在下一节中，我们将对CDAG进行更详细的描述。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>4.1.递归结构</b></p> <p>我们构造计算图<我>H</我><sub><i>我</我>＋1</年代ub>通过构造<我>12月</我><sub><i>我</我>＋1</年代ub><i>C</我>从<我>12月</我><sub><i>我</我></sub><i>C</我>而且<我>12月</我><sub>1</年代ub><i>C</我>,类似的构造<我>内附</我><sub><i>我</我>＋1</年代ub><i>一个</我>而且<我>内附</我><sub><i>我</我>＋1</年代ub><i>B</我>，然后将三个部分组合在一起。下面是递归构造的主要思想<我>12月</我><sub><i>我</我>＋1</年代ub><i>C</我>，这一点在<a href="#F7">图7</a>．</p> <ul class="acm"> <li>复制<我>12月</我><sub>1</年代ub><i>C</我>7<年代up><i>我</我></sup>次了。</li> <li>复制<我>12月</我><sub><i>我</我></sub><i>C</我>4倍。</li> <li>识别4·7<年代up><i>我</我></sup>的副本的顶点输出<我>12月</我><sub>1</年代ub><i>C</我>4·7<年代up><i>我</我></sup>的副本的输入顶点<我>12月</我><sub><i>我</我></sub><i>C</我>：<ul class="noneNested"> <li>-回忆每一个<我>12月</我><sub>1</年代ub><i>C</我>有四个输出顶点。</li> <li>-集合的每个第一个输出顶点的7<年代up><i>我</我></sup><i>12月</我><sub>1</年代ub><i>C</我>图被标识为集合7<年代up><i>我</我></sup>的第一个副本的输入顶点<我>12月</我><sub><i>我</我></sub><i>C</我>．</li> <li>-集合的每一秒输出顶点的7<年代up><i>我</我></sup><i>12月</我><sub>1</年代ub><i>C</我>图被标识为集合7<年代up><i>我</我></sup>的第二个副本的输入顶点<我>12月</我><sub><i>我</我></sub><i>C</我>等等。</li> <li>-我们确保<我>j</我><sup>th</年代up>的一个副本的输入顶点<我>12月</我><sub><i>我</我></sub><i>C</我>的输出顶点与<我>j</我><sup>th</年代up>的副本<我>12月</我><sub>1</年代ub><i>C</我>．</li> </ul></li> </ul> <p>在构建<我>内附</我><sub><i>我</我>＋1</年代ub><i>一个</我>而且<我>内附</我><sub><i>我</我>＋1</年代ub><i>B</我>以类似的方式，我们得到<我>H</我><sub><i>我</我>＋1</年代ub>通过连接从<我>k</我><sup>th</年代up>输出的顶点<我>内附</我><sub><i>我</我>＋1</年代ub><i>一个</我>而且<我>内附</我><sub><i>我</我>＋1</年代ub><i>B</我>到<我>k</我><sup>th</年代up>输入的顶点<我>12月</我><sub><i>我</我>＋1</年代ub><i>C</我>，对应于元素级标量乘法。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>4.2.Strassen边缘扩张</b></p> <p>给定Strassen算法的CDAG的构造，我们现在陈述我们关于解码图的边缘展开的主要引理。证明技术类似于阿隆等人的扩张器分析。<年代up><a href="#R2">2</a></sup>完整的证明，见巴拉德等人。<年代up><a href="#R10">10</a></sup></p> <p>引理5。(主要引理)<我>12月边缘扩张</我><sub><i>k</我></sub><i>C</我>是</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/4fbaffcb-47f1-4961-93e6-0e088ac238b7/ueq07.gif" border="0" hspace="2" vspace="5" alt="ueq07.gif"></p> <p>通过另一个论点(巴拉德等人的证明。<年代up><a href="#R10">10</a></sup>)，我们就得到了</p> <p align="center"><img src="https://dl.acm.org/cms/attachment/2d5d070c-e634-4629-a842-f1731e39df69/ueq08.gif" border="0" hspace="2" vspace="5" alt="ueq08.gif"></p> <p>在哪里<我>年代</我>= (7<年代up><i>k</我></sup>)．选择<我>年代</我>= (<我>米</我><sup><img src="https://dl.acm.org/cms/attachment/ed34bcd7-8870-486b-ad44-8d423e3eb199/cacm5702_o.gif" border="0" hspace="2" alt="cacm5702_o.gif"></sup>)，我们满足不等式4并得到不等式5(对于足够大的|<我>V</我>|)。这就得到定理1。</p> <p class="totop"><a href="#PageTop">回到顶部</a></p> <a name="body-6"></a> <h3>5.扩展</h3.．> <p>本文研究了两种机器模型上Strassen矩阵乘法的下界问题。然而，通过通信最小化改进基本算法的设计空间要大得多。它包括证明下界和开发最优算法;使用经典方法以及快速算法，如Strassen的;执行矩阵乘法，其他矩阵算法，和更一般的计算;尽量减少时间和/或精力;使用最小内存或牺牲额外内存以换取更少的通信;并使用层次、同构或异构的顺序和并行模型。在本节中，我们将讨论这些扩展的一个子集;参见巴拉德等人。<年代up><a href="#R9">9</a>, 10</年代up>并参考其中的更多细节。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>5.1.下界</b></p> <p>第3节所描述的证明技术并不是Strassen算法所特有的，它可以被更广泛地应用。在数值线性代数中，划分参数被广泛应用于经典算法中<年代up><a href="#R8">8</a>, 20</年代up>其中一个几何不等式指定了每段的通信成本，而不是边扩展。进一步，边缘展开技术适用于<我>Strassen-like</我>方阵相乘的算法<我>o</我>（<我>n</我><sup>3.</年代up>)算术运算，到其他快速算法的矩形矩阵乘法，以及其他矩阵计算。</p> <p><b>Strassen-like算法</b>．类strassen算法是一种基于矩阵相乘方案的递归矩阵乘法算法<我>k</我>×<我>k</我>矩阵使用<我>问</我>一些是标量乘法<我>k</我>而且<我>q < k</我><sup>3.</年代up>(这样算法才能执行<我>O</我>（<我米g src="https://dl.acm.org/cms/attachment/f313c074-d40f-4227-a97a-521922da30ce/cacm5702_p.gif" border="0" hspace="2" alt="cacm5702_p.gif">)失败<我></i><sub>0</年代ub>=日志<年代ub><i>k</我></sub><i>问</我>)。有关矩阵乘法运算复杂度的最新边界和对以前边界的引用，请参阅Williams。<年代up><a href="#R25">25</a></sup>为了应用我们的下界证明，我们需要strassen类算法的另一个技术标准:解码图必须是连接的。这类算法包括许多(但不是全部)快速矩阵乘法。有关详细信息和示例，请参见Ballard等人。<年代up><a href="#R7">7</a>, 10</年代up></p> <p>对于类strassen算法，通信下界的表述与定理1、推论2和定理3的形式相同:replace log<年代ub>2</年代ub>7与<我></i><sub>0</年代ub>到处都看起来!证明技术遵循Strassen的算法。而经典算法的边界具有相同的形式，取代了log<年代ub>2</年代ub>7和3，证明的技巧就大不相同了。<年代up><a href="#R18">18</a>, 20</年代up></p> <p><b>快速矩形矩阵乘法</b>．许多快速算法已经被设计用于矩形矩阵的乘法(见Ballard等人)。<年代up><a href="#R7">7</a></sup>查看详细列表)。乘法的快速算法<我>米</我>×<我>k</我>而且<我>k</我>×<我>r</我>矩阵中<我>问</我><<我>mkr</我>标量乘法可以递归地应用于乘法<我>米</我><sup><i>t</我></sup>×<我>k</我><sup><i>t</我></sup>而且<我>k</我><sup><i>t</我></sup>×<我>r</我><sup><i>t</我></sup>矩阵中<我>O</我>（<我>问</我><sup><i>t</我></sup>)失败。对于这类算法，CDAG的结构与Strassen和类Strassen的平方乘法算法非常相似，它由两个编码图和一个解码图组成。假设解码图是连通的，定理1和引理5的证明适用于我们插入的地方<我>先生</我>而且<我>问</我>4和7。在这种情况下，我们得到了一个类似于定理1的结果，该结果表明，这种算法的通信代价由(<我>问</我><sup><i>t</我></sup><i>/ M</我><sup><img src="https://dl.acm.org/cms/attachment/2a80810e-1d71-4201-a055-5c942c19afb6/cacm5702_q.gif" border="0" hspace="2" alt="cacm5702_q.gif"></sup>)．如果输出矩阵是三个矩阵中最大的(即，<我>k</我><<我>米</我>而且<我>k</我><<我>r</我>)，则该下界是由自然递归算法得到的，因此是紧的。下界也可以推广到并行情况，类似于推论2，并可以使用Ballard等人的算法技术得到。<年代up><a href="#R6">6</a></sup></p> <p><b>剩下的数值线性代数</b>．快速矩阵乘法算法是线性代数中许多快速算法的基本组成部分，如LU算法，QR算法，特征值和奇异值分解算法。<年代up><a href="#R13">13</a></sup>因此，这些算法的通信代价下界可以由快速矩阵乘法算法的下界导出。例如，当LU算法在足够大的子矩阵上调用快速矩阵乘法算法时，LU上的下界(或QR等)就会出现。Demmel等人的算法就是这样，<年代up><a href="#R13">13</a></sup>然后我们就可以推导出匹配的下界和上界。<年代up><a href="#R10">10</a></sup></p> <p><b>嵌套循环计算</b>．几乎所有证明通信下界的论据都是建立在一组给定数据和可用这些数据进行的有用计算量之间的关系，即所谓的“面体积比”(surface-to-volume)。例如，Hong和Kung<年代up><a href="#R18">18</a></sup>利用cdg的显性集和最小集的分析来建立这样的比率。LoomisWhitney几何不等式被用于这个目的，在Ballard等人的三个嵌套循环指定的矩阵计算。<年代up><a href="#R8">8</a></sup>和Irony等人。<年代up><a href="#R20">20.</a></sup>最近，克里斯特等人。<年代up><a href="#R12">12</a></sup>使用了卢米斯·惠特尼不等式(即HölderBrascampLieb不等式)的推广来扩展这一分析，以证明计算的下界，这些计算由任意一组线性访问数组并满足某些其他条件的嵌套循环指定。</p> <p><img src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊"><b>5.2.算法</b></p> <p>追求通信下界的主要动机是为算法的性能提供目标。事实上，定理1和推论2的猜想和证明，以及序列情况下最优算法的存在，是改进Strassen算法并行实现的主要动机。我们不仅能够设计出一种最优算法，而且还能够通过分布式内存机器的实现展示它在实践中执行得更快。<年代up><a href="#R6">6</a>21岁</年代up></p> <p><b>通信避免平行斯特拉森</b>．在第2.2节中，我们说明了一个新的并行Strassen矩阵乘法算法的通信代价，匹配渐近下界。该算法的细节出现在Ballard等人，<年代up><a href="#R6">6</a></sup>Lipshitz等给出了更广泛的实现细节和性能数据。<年代up><a href="#R21">21</a></sup>我们证明了新算法比我们已知的任何其他并行矩阵乘法算法，包括基于经典算法的并行矩阵乘法算法和基于Strassen算法的并行矩阵乘法算法都更高效。</p> <p><a href="#F1">图1</a>显示Cray XT4上的性能。有关其他机器上的结果，请参阅Lipshitz等人。<年代up><a href="#R21">21</a></sup>例如，在一个有10,000个核的Cray XE6上运行，以解决维度问题<我>n</我>= 131712时，我们的新算法对经典矩阵乘法的性能比峰值高出30%，比最佳经典实现高出83%，比Strassen算法之前的最佳实现高出75%。即使是很小的维度问题<我>n</我>= 4704，它的性能比最好的经典实现高66%。</p> <p><b>进一步的应用</b>．我们并行实现Strassen算法的关键算法思想是对递归树进行仔细的并行遍历。这种想法适用于许多其他递归算法，其中子问题不具有相互依赖关系(在存在依赖关系的某些情况下也适用)。例如，经典的矩形矩阵乘法<年代up><a href="#R14">14</a></sup>稀疏矩阵矩阵乘法<年代up><a href="#R4">4</a></sup>可以通过这种并行化方式来获得通信的最优化。</p> <p>同样的技术可以用于在算法层面节省能量(因为通信比计算消耗更多的能量)，以及获得能量需求的下限。<年代up><a href="#R15">15</a></sup></p> <p>总之，我们相信从算法开发到高效实现的理论下界的工作流程是非常有效的:通过在算法级别考虑基础计算，许多应用程序的显著改进是可能的。</p> <p class="totop"><a href="#PageTop">回到顶部</a></p> <a name="body-7"></a> <h3>致谢</h3.．> <p>我们要感谢Benjamin Lipshitz在这些想法上所做的工作，以及在撰写本文期间所做的有益讨论。</p> <p>这项工作得到了微软(奖#024263)和英特尔(奖#024894)的资助，并得到了U.C. Discovery(奖#DIG07-10227)的匹配资助;Par Lab子公司国家仪器、NEC、诺基亚、NVIDIA和三星的额外支持也得到了认可。该研究由美国能源部拨款支持，拨款编号为DE-SC0003959、DE-SC0004938、DE-SC0005136、DE-SC0008700、AC02-05CH11231和DE-FC02-06-ER25786, DARPA拨款编号为HR0011-12-2-0016。该研究还得到了亚历山大·冯·洪堡基金会的Sofja Kovalevskaja项目和国家科学基金会DMS-0635607协议的支持，以及ERC启动资金编号239985的支持。</p> <p class="totop"><a href="#PageTop">回到顶部</a></p> <div id="article-references"> <a name="references"></a> <h3 class="known-headings">参考文献</h3.．> <p><a name="R1"></a>1.Agarwal, r.c.， Balle, s.m.， Gustavson, f.g.， Joshi, M.， Palkar, P.平行矩阵乘法的三维方法。<我>IBM J. Res. Dev</我>， 5(1995)， 575582。</p> <p><a name="R2"></a>2.阿隆，N.，施瓦茨，O.，夏皮拉，A.恒度扩张器的基本构造。<我>选择符。Probab。第一版。17</我>， 3(2008)， 319327。</p> <p><a name="R3"></a>3.Anderson, E.， Bai, Z.， Bischof, C.， Demmel, J.， Dongarra, J.， Croz, J.D.， Greenbaum, A.， Hammarling, S.， McKenney, A.， Ostrouchov, S.， Sorensen, D. LAPACK的用户指南，工业和应用数学协会，费城，宾夕法尼亚州，美国，1992。也可以从<a href="http://www.netlib.org/lapack/">http://www.netlib.org/lapack/</a>．</p> <p><a name="R4"></a>4.巴拉德，G.， Buluç， A.， Demmel, J.， Grigori, L.， Lipshitz, B.， Schwartz, O.， Toledo, S.稀疏随机矩阵的通信最优并行乘法。在<我>第25届美国计算机学会并行算法与体系结构研讨会论文集</我>， (2013)， ACM，纽约，纽约，美国。</p> <p><a name="R5"></a>5.Ballard, G.， Demmel, J.， Holtz, O.， Lipshitz, B.， Schwartz, O.简短声明:矩阵乘法算法的强缩放和与内存无关的通信下界。在<我>第24届美国计算机学会并行算法与体系结构研讨会论文集</我>， (2012)， ACM，纽约，纽约，美国，7779。</p> <p><a name="R6"></a>6.Ballard, G.， Demmel, J.， Holtz, O.， Lipshitz, B.， Schwartz, O.用于Strassen矩阵乘法的通信最优并行算法。在<我>第24届美国计算机学会并行算法与体系结构研讨会论文集</我>， SPAA '12 (2012)， ACM，纽约，纽约，美国，193204。</p> <p><a name="R7"></a>7.Ballard, G.， Demmel, J.， Holtz, O.， Lipshitz, B.， Schwartz, O.矩形矩阵快速乘法通信代价的图展开分析。在<我>算法设计与分析</我>．G. Even和D. Rawitz，编辑。，第7659卷<我>计算机科学课堂讲稿</我>(2012)，施普林格，柏林-海德堡，1336。</p> <p><a name="R8"></a>8.巴拉德，德梅尔，J.，霍兹，O.，施瓦茨，O.图展开和矩阵快速乘法的通信成本。在<我>第23届ACM并行算法与体系结构年会论文集</我>(2011)， ACM，纽约，纽约，美国，112。</p> <p><a name="R9"></a>9.Ballard, G.， Demmel, J.， Holtz, O.， Schwartz, O.最小化数值线性代数中的通信。<我>矩阵肛门。: 32。</我>， 3(2011)， 866901。</p> <p><a name="R10"></a>10.巴拉德，德梅尔，J.，霍兹，O.，施瓦茨，O.图展开和矩阵快速乘法的通信成本。<我>j . ACM</我>(2012年12月)<我>59</我>6 32:132:23。</p> <p><a name="R11"></a>11.大炮,L。<我>用蜂窝计算机实现了卡尔曼滤波算法</我>．博士论文，蒙大拿州立大学，博兹曼，蒙大拿州(1969)。</p> <p><a name="R12"></a>12.Christ, M.， Demmel, J.， Knight, N.， Scanlon, T.， Yelick, K.通信下界和最优算法，程序引用数组第一部分，手稿，2013。</p> <p><a name="R13"></a>13.Demmel, I. Dumitriu, I. Holtz, O.快速线性代数是稳定的。<我>号码。108年数学。</我>， 1(2007)， 5991。</p> <p><a name="R14"></a>14.Demmel, J.， Eliahu, D.， Fox, A.， Kamil, S.， Lipshitz, B.， Schwartz, O.， Spillinger, O.通信-最优并行递归矩形矩阵乘法。在<我>第27届IEEE国际并行与分布式处理研讨会论文集</我>（<我>IPDPS</我>)(2013年),IEEE。</p> <p><a name="R15"></a>15.Demmel, J.， Gearhart, A.， Lipshitz, B.， Schwartz, O.完美的强缩放不需要额外的能量。在<我>第27届IEEE国际并行与分布式处理研讨会论文集</我>， ipdps '13 (2013)， ieee;</p> <p><a name="R16"></a>16.富勒，s.h.，米莱特，l.i.，编辑。<我>计算性能的未来:游戏结束还是下一个阶段?</我>国家科学院出版社，华盛顿特区，2011年，200页，<a href="http://www.nap.edu">http://www.nap.edu</a>．</p> <p><a name="R17"></a>17.格雷厄姆，s.l.，斯尼尔，M，帕特森，c.a.编辑。<我>《赶上速度:超级计算的未来</我>．国家科学院国家研究委员会报告。国家科学院出版社，华盛顿特区，2004年，289页，<a href="http://www.nap.edu">http://www.nap.edu</a>．</p> <p><a name="R18"></a>18.Hong, j.w.， Kung, H.T. I/O复杂性:红蓝鹅卵石游戏。在<我>第13届ACM计算理论年会论文集</我>(1981)， ACM，纽约，美国，326333。</p> <p><a name="R19"></a>19.Hoory, S.， Linial, N.， Wigderson A.。<我>公牛。AMS 43</我>(4),(2006), 439561。</p> <p><a name="R20"></a>20.反语，D.，托莱多，S.，提斯金，A.分布式存储矩阵乘法的通信下界。<我>j . Distrib平行。64年第一版。</我>， 9，(2004)， 10171026。</p> <p><a name="R21"></a>21.利普希茨，B.，巴拉德，G.，德梅尔，J.，施瓦兹，O.。在<我>高性能计算、网络、存储和分析国际会议论文集</我>， (2012)， IEEE计算机学会出版社，Los Alamitos, CA, USA, 101:1101:11。</p> <p><a name="R22"></a>22.王志强，王志强，王志强，等。BSP模型中的内存效率矩阵乘法。<我>Algorithmica 24</我>(1999), 287297。</p> <p><a name="R23"></a>23.李志强，李志强，李志强。通信最优并行2.5D矩阵乘法和LU因子分解算法。在<我>第十七届欧洲并行与分布式计算国际会议论文集</我>(2011),施普林格。</p> <p><a name="R24"></a>24.高斯消去不是最优的。<我>号码。数学。13</我>(1969), 354356。</p> <p><a name="R25"></a>25.做矩阵乘法的速度比Coppersmith-Winograd快。在<我>第44届计算理论研讨会论文集</我>， STOC '12 (2012)， ACM，纽约，纽约，美国，887898。</p> </div> <p class="totop"><a href="#PageTop">回到顶部</a></p> <div id="article-authorinfo"> <a name="authorinfo"></a> <h3 class="known-headings">作者</h3.．> <p><b>灰色巴拉德</b>（<a href="mailto:ballard@eecs.berkeley.edu">ballard@eecs.berkeley.edu</a>)，加州大学伯克利分校电气工程与计算机科学系，加州。</p> <p><b>詹姆斯Demmel</b>（<a href="mailto:demmel@cs.berkeley.edu">demmel@cs.berkeley.edu</a>)，加州大学伯克利分校数学与计算机科学系，加州。</p> <p><b>奥尔加霍尔兹</b>（<a href="mailto:holtz@math.berkeley.edu">holtz@math.berkeley.edu</a>)、加州大学伯克利分校数学系和德国柏林理工大学数学研究所für Mathematik。</p> <p><b>欧迪施瓦兹</b>（<a href="mailto:odedsc@eecs.berkeley.edu">odedsc@eecs.berkeley.edu</a>)，加州大学伯克利分校电气工程与计算机科学系，加州。</p> </div> <p class="totop"><a href="#PageTop">回到顶部</a></p> <div id="article-footnotes"> <a name="footnotes"></a> <h3 class="known-headings">脚注</h3.．> <p>本文的原始版本题为“快速矩阵乘法的图扩展和通信成本”，首次发表在<我>2011年美国计算机学会并行算法与架构研讨会论文集</我>也出现在2012年12月号的<我>美国计算机学会杂志</我>．</p> </div> <p class="totop"><a href="#PageTop">回到顶部</a></p> <div id="article-figures"> <a name="figures"></a> <h3 class="known-headings">数据</h3.．> <p class="ThumbnailParagraph"><a name="F1"></a><a href="https://dl.acm.org/cms/attachment/7f76eee6-a5a7-49c7-a3c8-b4251133b923/f1.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/a172978c-96d2-49bb-bfb4-5a64e23ad863/f1.jpg" border="0" alt="F1"></a>图1。Cray XT4上并行矩阵乘法算法的强尺度性能比较。<年代up>6</年代up>所有数据都对应于一个固定的维度<我>n</我>= 94080。的<我>x</我>-axis表示处理器数量<我>p</我>在对数尺度上<我>y</我>-轴衡量有效的表现，或2<我>n</我><sup>3.</年代up>/（<我>p</我>·时间)。新算法优于所有其他已知算法，并超过了与经典触发器计数有关的机器的峰值性能。对于这个问题规模，新算法比之前最好的strassen算法快24184%，比最好的经典算法快5184%。</p> <p class="ThumbnailParagraph"><a name="F2"></a><a href="https://dl.acm.org/cms/attachment/4d0c3b6e-5d62-4ce1-a533-7f71c8620c7a/f2.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/0feb5781-c54c-4281-acfe-50b8cb7a88ee/f2.jpg" border="0" alt="F2"></a>图2。顺序两级(左)和并行分布式内存(右)模型。</p> <p class="ThumbnailParagraph"><a name="F3"></a><a href="https://dl.acm.org/cms/attachment/fb144b0c-38bd-4455-8bf4-72eedef6dcde/f3.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/5bc40de8-bddc-44c0-9c17-9eb4d1aa2614/f3.jpg" border="0" alt="F3"></a>图3。沟通成本和矩阵乘法的强扩展性:经典vs. Strassen。<年代up>5</年代up>纵轴对应于<我>p</我>乘以通信成本，所以水平线对应完美的强缩放。的数量<我>p</我><sub>最小值</年代ub>是存储输入输出矩阵所需的最小处理器数量(即<我>p</我><sub>最小值</年代ub>= 3<我>n</我><sup>2</年代up>/<我>米</我>在哪里<我>n</我>矩阵维数是和吗<我>米</我>是本地内存大小)。</p> <p class="ThumbnailParagraph"><a name="F4"></a><a href="https://dl.acm.org/cms/attachment/7efa58b9-acb2-4a6a-ba68-c489994ceeee/f4.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/075f6674-86a4-4ad9-9e08-7229ce425873/f4.jpg" border="0" alt="F4"></a>图4。一个子集(段)<我>年代</我>和它对应的读操作数<我>R</我><sub><i>年代</我></sub>和写操作数<我>W</我><sub><i>年代</我></sub>．</p> <p class="ThumbnailParagraph"><a name="F5"></a><a href="https://dl.acm.org/cms/attachment/7b89e9cc-8a5c-4e94-991e-3f184d3865d9/f5.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/84b6aab7-8eee-4226-bbbf-ec6b821bdc20/f5.jpg" border="0" alt="F5"></a>图5。Strassen 2 × 2矩阵相乘算法的计算图(<我>H</我><sub>1</年代ub>)．的编码<我>一个</我>而且<我>B</我>对应算法3第410行加减法，以及对7次乘法的解码计算<我>C</我>对应于第1114行。带两个指标的顶点<我>ij</我>对应于(<我>我,我</我>）<年代up>th</年代up>矩阵的一个项和一个标为一个下标的顶点<我>k</我>对应于<我>k</我><sup>th</年代up>中间的乘法。</p> <p class="ThumbnailParagraph"><a name="F6"></a><a href="https://dl.acm.org/cms/attachment/8f0d4c08-8d07-4ac2-9de2-fea7739a91e7/f6.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/be6909ef-2a69-41e6-991c-a5a290bd8df1/f6.jpg" border="0" alt="F6"></a>图6。对Strassen的CDAG的高层观点<我>n</我>×<我>n</我>矩阵。该图由两个编码子图和一个解码子图组成;子图之间的连接没有显示。</p> <p class="ThumbnailParagraph"><a name="F7"></a><a href="https://dl.acm.org/cms/attachment/4e59819f-57c7-4e81-b713-e218a2dd5a34/f7.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/164ebca8-585a-42ce-863d-ef3678f0f929/f7.jpg" border="0" alt="F7"></a>图7。译码子图的递归构造的示例。构建<我>12月</我><sub><i>我</我>＋1</年代ub><i>C, 12月</我><sub><i>我</我></sub><i>C</我>被复制了4次<我>12月</我><sub>1</年代ub><i>C</我>复制7<年代up><i>我</我></sup>确定时间和适当的顶点。</p> </div> <p class="totop"><a href="#PageTop">回到顶部</a></p> <div id="article-tables"> <a name="tables"></a> <h3 class="known-headings">表</h3.．> <p class="ThumbnailParagraph"><a name="T1"></a><a href="https://dl.acm.org/cms/attachment/a988f7af-6469-4155-91a4-db3126c9f051/t1.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/fdd65911-1e6a-4dfe-9203-2c9bc9f5e92d/t1.jpg" border="0" alt="T1"></a>表1。序列矩阵乘法的渐近通信代价下界，其中<我>n</我>矩阵维数是和吗<我>米</我>是快速内存大小。注意，虽然古典和Strassen的表达式是相似的，但证明技术是相当不同的</p> <p class="ThumbnailParagraph"><a name="T2"></a><a href="https://dl.acm.org/cms/attachment/69e349d1-2f06-40a7-8924-1986270c7579/t2.jpg" class="ThumbnailLink"><img src="https://dl.acm.org/cms/attachment/776a903f-2000-42b0-bf4c-044486e7b4ed/t2.jpg" border="0" alt="T2"></a>表2。并行矩阵乘法的渐近通信代价下界，其中<我>n</我>矩阵维数,<我>米</我>是本地内存大小，和<我>p</我>是处理器的数量吗</p> </div> <p class="totop"><a href="#PageTop">回到顶部</a></p> <div id="article-permission"> <hr class="Separator"> <a name="permission"></a> <p><b>©2014 0001 - 0782/14/02 ACM</b></p> <p>如果您不是为了盈利或商业利益而制作或分发本作品的部分或全部，并在第一页注明本通知和完整引用，则允许您免费制作本作品的部分或全部数字或纸质副本，供个人或课堂使用。本作品的组成部分必须由ACM以外的其他人享有版权。信用文摘是允许的。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或费用。请求发布的权限<a href="mailto:permissions@acm.org">permissions@acm.org</a>或传真(212)869-0481。</p> </div> <p>数字图书馆是由计算机协会出版的。版权所有©2014 ACM股份有限公司</p> <div class="clearer"></div> <hr class="thick"> <a name="comments"></a> <div id="ArticleComments"> <span id="CommentHeader"></span> </div> <p class="view-all">没有发现记录</p> </div> <div class="col3 floatLeft lastCol"> <div class="signInWidget widget"> <span class="signInTitle">登录<年代pan class="noTransform">为完全访问</年代pan></span> <form action="//www.eqigeno.com/login" method="post"> <div class="portaInputSignIn"> <label for="inputUser" class="inField">用户名</label> <input name="current_member[user]" type="text" id="inputUser"> </div> <div class="portaInputSignIn"> <label for="inputPassword" class="inField">密码</label> <input type="password" name="current_member[passwd]" id="inputPassword"> </div> <a href="//www.eqigeno.com/accounts/forgot-password" class="subText">»忘记密码?</a> <a href="//www.eqigeno.com/accounts/new" class="subText"><strong>*创建ACM Web帐户</年代trong></a> <button type="submit" class="submitSignIn">登录</button> </form> </div> <div id="article-contents-widget" class="widget contentsWidget"> <h6 class="loud">文章内容:</h6> <ul> <li class="miniWidgetItem"><a href="#body-1">摘要</a></li> <li class="miniWidgetItem"><a href="#body-2">1.简介</a></li> <li class="miniWidgetItem"><a href="#body-3">2.沟通下界</a></li> <li class="miniWidgetItem"><a href="#body-4">3.证明了</a></li> <li class="miniWidgetItem"><a href="#body-5">4.Strassen CDAG</a></li> <li class="miniWidgetItem"><a href="#body-6">5.扩展</a></li> <li class="miniWidgetItem"><a href="#body-7">致谢</a></li> <li class="miniWidgetItem"><a href="#references">参考文献</a></li> <li class="miniWidgetItem"><a href="#authorinfo">作者</a></li> <li class="miniWidgetItem"><a href="#footnotes">脚注</a></li> <li class="miniWidgetItem"><a href="#figures">数据</a></li> <li class="miniWidgetItem"><a href="#tables">表</a></li> </ul> </div> <div id="SideColumn"> <div id="related-news-opinion-widget" class="blueWidget widget noBottom" data-swiftype-index="false"> <span class="widgetName">更多新闻和观点</年代pan> <div class="singleNews firstNews"> <h5><a href="//www.eqigeno.com/news/259696-europeans-wary-of-new-digital-identity">欧洲人警惕新的数字身份</a></h5> <span class="dateNews">Arnout雅斯贝尔斯<br>由中华航空公司职员委托</年代pan> </div> <div class="singleNews"> <h5><a href="//www.eqigeno.com/opinion/articles/260525-is-ai-threatened-by-too-little-data">人工智能是否受到数据太少的威胁?</a></h5> <span class="dateNews">TechRepublic</年代pan> </div> <div class="singleNews"> <h5><a href="//www.eqigeno.com/blogs/blog-cacm/257644-cultivating-habits-1-2-for-researchers">培养习惯:研究人员-1 +2</a></h5> <span class="dateNews">巴格奇Saurabh</年代pan> </div> </div> </div> </div> <a class=" hidden video-link" href="//www.eqigeno.com/magazines/2014/2/171673-communication-costs-of-strassens-matrix-multiplication"></a> </section> <button class="to-top"></button> <footer> <nav> <ul> <li class="first-child"><a href="//www.eqigeno.com/about-communications/author-center" title="对于作者">对于作者</a></li> <li><a href="https://www.acm.org/publications/advertising" title="为广告客户" target="_blank">为广告客户<我米g src="//www.eqigeno.com/images/icons/new_page.png" alt="为广告客户"></a></li> <li><a href="//www.eqigeno.com/privacy" title="隐私政策">隐私政策</a></li> <li><a href="//www.eqigeno.com/help" title="帮助">帮助</a></li> <li><a href="//www.eqigeno.com/about-communications/contact-us" title="联系我们">联系我们</a></li> <li><a class="toggle-mobile" href="https://m-www.eqigeno.com/magazines/2014/2/171673-communication-costs-of-strassens-matrix-multiplication/fulltext?mobile=true" data-domain="www.eqigeno.com">手机网站</a></li> </ul> </nav> <span id="footerText">vwin德赢ac米兰合作</span> </footer> </div> </div>  <div style="text-align:center;margin-bottom:5px;"><form action="http://www.baidu.com/baidu" target="_blank"><div bgcolor="#FFFFFF" style="text-align:center;"><input name="tn" type="hidden" value="baidu"><a href="http://www.baidu.com/"><img src="http://img.baidu.com/img/logo-80px.gif" width="80px" height="29px" alt="Baidu" align="bottom" border="0"></a><input type="text" name="word" size="30" placeholder="" value=""><input type="submit" value="baidusousou"></div></form></div><div id="so360" style="text-align:center;margin-bottom:5px;"><form action="https://www.so.com/" target="_blank" id="so360form"><img src="http://p1.qhimg.com/d/_onebox/search.png" width="100px" height="25px"> <input type="text" autocomplete="off" name="q" id="so360_keyword" placeholder="" value=""> <input type="submit" id="so360_submit" value="360sousou"> <input type="hidden" name="ie" value="gbk"><input type="hidden" name="src" value="zz"> <input type="hidden" name="site" value="so.com"> <input type="hidden" name="rg" value="1"></form></div><div id="sogou" style="text-align:center;margin-bottom:5px;"><form action="https://www.sogou.com/" target="_blank" id="so360form"><img src="https://www.sogou.com/web/index/images/logo_440x140.v.4.png" width="100px" height="25px"> <input type="text" autocomplete="off" name="q" id="sogou.com_keyword" placeholder="" value=""> <input type="submit" id="sogou_submit" value="sougou"> <input type="hidden" name="ie" value="gbk"><input type="hidden" name="src" value="zz"> <input type="hidden" name="site" value="so.com"> <input type="hidden" name="rg" value="1"></form></div><div align="center"><a target="_blank" href="/sitemap.xml">map</a></div></body> </html>