{"id":171416,"date":"2014-10-17T13:27:33","date_gmt":"2014-10-17T13:27:33","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/project\/parasail\/"},"modified":"2021-03-09T12:33:18","modified_gmt":"2021-03-09T20:33:18","slug":"parasail","status":"publish","type":"msr-project","link":"https:\/\/www.microsoft.com\/en-us\/research\/project\/parasail\/","title":{"rendered":"Parasail"},"content":{"rendered":"<p>Project Parasail\u00a0is a novel approach to parallelizing a large class of seemingly sequential applications wherein dependencies are, at runtime, treated as symbolic values. The efficiency of parallelization, then, depends on the efficiency of the symbolic computation, an active area of research in static analysis, verification, and partial evaluation. This is exciting as advances in these fields can translate to novel parallel algorithms for sequential computation.<\/p>\n<p><iframe loading=\"lazy\" title=\"Efficient Parallelization Using Rank Convergence in Dynamic Programming Algorithms\" src=\"https:\/\/player.vimeo.com\/video\/184001139?dnt=1&app_id=122963\" width=\"500\" height=\"281\" frameborder=\"0\" allow=\"autoplay; fullscreen; picture-in-picture; clipboard-write\"><\/iframe><\/p>\n\t\t\t<div class=\"moray-accordion\" data-show=\"false\">\n\t\t\t\t\t\t\t<div class=\"clearfix\">\n\t\t\t\t\t<div\n\t\t\t\t\t\tclass=\"btn-group align-items-center mb-g float-sm-right\"\n\t\t\t\t\t\trole=\"group\"\n\t\t\t\t\t\tdata-mount=\"collapse-controls\"\n\t\t\t\t\t\tdata-bi-aN=\"accordion-collapse-controls\"\n\t\t\t\t\t\tdata-target=\"#accordion-1\">\n\t\t\t\t\t\t<button class=\"btn btn-link m-0\" aria-disabled=\"false\" aria-pressed=\"false\" data-action=\"expand\" type=\"button\" data-bi-cN=\"Expand all\">Expand all<\/button>\n\t\t\t\t\t\t<span aria-hidden=\"true\"> | <\/span>\n\t\t\t\t\t\t<button class=\"btn btn-link m-0\" aria-disabled=\"false\" aria-pressed=\"false\" data-action=\"collapse\" type=\"button\" data-bi-cN=\"Collapse all\">Collapse all<\/button>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<ul class=\"accordion\" id=\"accordion-1\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t<li class=\"m-0\">\n\t\t\t<h4 class=\"accordion-header\">\n\t\t\t\t<button\n\t\t\t\t\tclass=\"btn btn-collapse m-0\"\n\t\t\t\t\ttype=\"button\"\n\t\t\t\t\tdata-mount=\"collapse\"\n\t\t\t\t\tdata-target=\"#collapse-2\"\n\t\t\t\t\taria-expanded=\"false\"\n\t\t\t\t\taria-controls=\"collapse-2\">\n\t\tProject Parasail in the News\t\t\t\t<\/button>\n\t\t\t<\/h4>\n\t\t\t<div class=\"collapse\" id=\"collapse-2\">\n\t\t\t\t<div class=\"accordion-body\">\n\t\t\t\t\t\t\t\t\t\t<ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/cacm.acm.org\/magazines\/2016\/10\/207775-efficient-parallelization-using-rank-convergence-in-dynamic-programming-algorithms\/abstract\">CACM Research Highlights article<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/li>\n<\/ul>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/li>\n\t\t\t\t\t\t\t\t\t<\/ul>\n\t\t<\/div>\n\t\t\n<p>Here&#8217;s an example of how it works. Imagine an algorithm that has three components, F, G, and H. F takes some data as input and generates a result. That result is used by G, possibly along with some other data, to compute\u00a0<em>its\u00a0<\/em>result. Then H uses G&#8217;s result (and again, possibly some other data) to compute the final result.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-299936\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2016\/09\/Sequential-300x183.png\" alt=\"sequential\" width=\"300\" height=\"183\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/09\/Sequential-300x183.png 300w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/09\/Sequential.png 590w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>Because of these dependencies, G cannot start executing until F has finished. Likewise, H cannot start executing until G has finished. How can we possibly execute this algorithm in parallel? We do that by starting G (and H) at the same time as F. F executes using the real input data, but G and H are given a\u00a0<em>symbolic<\/em> input, x. They are then executed in a symbolic manner which generates a summary:\u00a0<em>g(x)<\/em> for G and\u00a0<em>h(x)<\/em> for H. A summary is itself a function that, given a concrete input, generates a concrete (i.e., <em>not<\/em> symbolic) output.\u00a0So\u00a0once F has computed its output, that is used by\u00a0<em>g(x)<\/em> to compute the output that is then used as input by\u00a0<em>h(x)<\/em>.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-299939\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2016\/09\/Parallel-300x193.png\" alt=\"parallel\" width=\"300\" height=\"193\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/09\/Parallel-300x193.png 300w, https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/09\/Parallel.png 551w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>The final, concrete, result is the same as that computed by the sequential algorithm. In order for this to be efficient, it must be possible to do two things:<\/p>\n<ol>\n<li>The summary of a component must be &#8220;small&#8221;: i.e., it must be concise enough so that it can be communicated easily in a parallel implementation to the process that will execute it on concrete input.<\/li>\n<li>The execution of a summary must be efficient (which is related to its size): if it takes as long to execute the summary as it does to execute the original component, then the parallel implementation will be no faster than the sequential algorithm.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Project Parasail\u00a0is a novel approach to parallelizing a large class of seemingly sequential applications wherein dependencies are, at runtime, treated as symbolic values. The efficiency of parallelization, then, depends on the efficiency of the symbolic computation, an active area of research in static analysis, verification, and partial evaluation. This is exciting as advances in these [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"research-area":[13560,13547],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-171416","msr-project","type-msr-project","status-publish","hentry","msr-research-area-programming-languages-software-engineering","msr-research-area-systems-and-networking","msr-locale-en_us","msr-archive-status-active"],"msr_project_start":"2014-10-17","related-publications":[168797,168643,168641,167640,166117,166118,163237],"related-downloads":[],"related-videos":[],"related-groups":[],"related-events":[],"related-opportunities":[],"related-posts":[],"related-articles":[],"tab-content":[],"slides":[],"related-researchers":[{"type":"user_nicename","display_name":"Madan Musuvathi","user_id":32766,"people_section":"Microsoft","alias":"madanm"},{"type":"user_nicename","display_name":"Jacob Nelson","user_id":36275,"people_section":"Microsoft","alias":"jacnels"},{"type":"user_nicename","display_name":"Olli Saarikivi","user_id":37700,"people_section":"Microsoft","alias":"olsaarik"},{"type":"guest","display_name":"Zixian Cai","user_id":731890,"people_section":"Interns","alias":""},{"type":"guest","display_name":"Roshan Dathathri","user_id":605892,"people_section":"Interns","alias":""},{"type":"guest","display_name":"Gurbinder Gill","user_id":731887,"people_section":"Interns","alias":""},{"type":"guest","display_name":"Abhinav Jangda","user_id":731899,"people_section":"Interns","alias":""},{"type":"guest","display_name":"Amir Hossein Nodehi Sabet","user_id":731905,"people_section":"Interns","alias":""},{"type":"guest","display_name":"Zhengyang Liu","user_id":731893,"people_section":"Interns","alias":""}],"msr_research_lab":[],"msr_impact_theme":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/171416"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-project"}],"version-history":[{"count":5,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/171416\/revisions"}],"predecessor-version":[{"id":731911,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/171416\/revisions\/731911"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=171416"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=171416"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=171416"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=171416"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=171416"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}