{"id":1071,"date":"2021-04-18T18:30:00","date_gmt":"2021-04-18T18:30:00","guid":{"rendered":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/?p=1071"},"modified":"2021-04-30T12:10:04","modified_gmt":"2021-04-30T12:10:04","slug":"designing-algorithms-for-parallel-computing","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/designing-algorithms-for-parallel-computing\/","title":{"rendered":"Designing algorithms for parallel computing"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Computers aren\u2019t getting faster anymore. Well, computers are still getting \u201cfaster\u201d but not in the traditional sense. The speed of computers
was historically given in terms of the clock speed or frequency of the Central Processing Unit (CPU).  After the introduction of the first commercial CPU in 1971 (The intel C4004 that I’ve attempted to capture the likeliness of above), the frequency of CPUs was increasing linearly in time until the early 2000s when the frequency of CPUs began to plateau. The reason for this is one of power efficiency and heat output. The heat output of CPU transistors increases with frequency and above a certain frequency it will become too much for the CPU to operate at safe temperatures (i.e. not melt).<\/p>\n

This issue meant that around 2004, semiconductor manufacturers decided to shift their CPU design philosophy from trying to increase clock speed to increasing the number of CPU cores on each chip. This had the effect of increasing the computational power of CPUs whilst maintaining safe temperatures. Heat is dissipated better from the multiple CPU cores running at moderate frequencies.  Another advantage of multiple CPU cores are that they are capable of running separate streams of instructions to each other which is the basis for parallel computing.<\/p>\n

The previous focus on clock speed of a single core CPU, plus the fact that it is generally easier, meant that historically the algorithms used in computer programming were based on serial execution in which the instructions in the algorithm are executed by the CPU one after another in a sequence. This is illustrated on the left had side of the figure below where the tasks \u201center\u201d and are processed one by one. The increasing prevalence of parallel computing hardware such as multicore processors and clusters of linked multicore processors has given rise to a new way of approaching algorithm design. If it is possible to design an algorithm such that certain instructions\\tasks can be computed simultaneously, then these tasks can be computed in parallel by several CPU cores (as illustrated on the left of the figure) to achieve a speed-up in the running time of the algorithm.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"Parallelvsserial\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

This often runs into a few challenges. For example, many of the serial algorithms that have been developed to perform certain computational\u00a0tasks that are dependent on the outcome of other tasks. This means that <\/span>dependent tasks often cannot be executed in parallel. An algorithm that\u00a0<\/span>consists of many dependent tasks will be difficult to redesign in a way that\u00a0<\/span>will benefit from parallelisation. Another challenge that is encountered is\u00a0<\/span>that new errors arise due to parallelisation. For example, the designer of a parallel <\/span>algorithm has to be very careful that parallel tasks that work on the same data <\/span>do not influence how that data appears in other tasks such that the result <\/span>varies depending on which task is completed first.<\/span><\/p>

Despite this, it is often worthwhile to try and overcome these challenges because of the resulting increase in speed of the algorithm. It’s likely to not just an immediate speed-up either as parallel algorithms will continue to increase in speed as more parallel cores become available.<\/p>

A simple example of an algorithm that can be sped up using parallelisation is an algorithm designed to sort a list. Consider splitting the list up into \\( N \\) smaller lists, where\u00a0\\( N \\)<\/span>\u00a0is the number of available parallel cores, and then sorting those smaller lists in parallel. These sorted lists can then be joined back together and the joined list can be sorted easily as it is just a list of sorted blocks. Sorting the list in this manner results in a speedup for lists of an appreciable size.<\/p>

Another example that is more relevant to statistics and OR is Monte-Carlo sampling (Check out STOR-i student Hamish’s 60 second stats post on Monte-Carlo for a review on how Monte-Carlo sampling works<\/a>). Consider the simple example of approximating \\( \\pi \\) using Monte-Carlo sampling. We typically do this by sampling randomly within a square that encloses a circle, such as the one shown below, and labelling points based on whether they fall into the circle or not. We can then approximately calculate\u00a0<\/span>\\( \\pi \\)\u00a0<\/span>by using the ratio of points that fall into the circle and those that don\u2019t. Consider splitting the square into four quarters. It would then be possible to perform Monte-Carlo sampling on each of these quarters on four parallel cores and then using all four ratios obtained to calculate\u00a0<\/span>\\( \\pi \\)\u00a0<\/span>. In this manner, we can perform more samples in the same amount of time, increasing the accuracy of the approximation.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"MCparallel\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

In general, parallelisation has the potential to speed up\u00a0<\/span>many of the algorithms that are essential in computational statistics and\u00a0<\/span>operational research such as the particle filter<\/a>\u00a0<\/span>or branch and bound methods for solving integer programs. In many of these\u00a0<\/span>cases, parallelisation requires the implementation of intelligent mathematical solutions to <\/span>try and overcome some of the dependency problems I discussed earlier.<\/span><\/p>

Relevant Links<\/span><\/p>

Paper on the parallelisation of advanced Monte Carlo methods<\/a><\/p>

Paper on parallelisation of branch and bound algorithm<\/a><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Computers aren\u2019t getting faster anymore. Well, computers are still getting \u201cfaster\u201d but not in the traditional sense. The speed of computerswas historically given in terms of the clock speed or frequency of the Central Processing Unit (CPU).  After the introduction of the first commercial CPU in 1971 (The intel C4004 that I’ve attempted to capture […]<\/p>\n","protected":false},"author":19,"featured_media":1080,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"slim_seo":{"title":"Designing algorithms for parallel computing - JACK TRAINER","description":"Computers aren\u2019t getting faster anymore. Well, computers are still getting \u201cfaster\u201d but not in the traditional sense. The speed of computers was historically gi"},"footnotes":""},"categories":[21,14,28],"tags":[19,24,32],"class_list":["post-1071","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computational-statistics","category-computer-science","category-operational-research","tag-algorithms","tag-monte-carlo","tag-parallel-computing"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/1071","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/users\/19"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/comments?post=1071"}],"version-history":[{"count":17,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/1071\/revisions"}],"predecessor-version":[{"id":1197,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/posts\/1071\/revisions\/1197"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/media\/1080"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/media?parent=1071"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/categories?post=1071"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/jack-trainer\/wp-json\/wp\/v2\/tags?post=1071"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}