{"id":125,"date":"2011-03-27T00:00:07","date_gmt":"2011-03-27T00:00:07","guid":{"rendered":"http:\/\/ajhassoc.com\/?p=125"},"modified":"2017-05-17T01:53:54","modified_gmt":"2017-05-17T01:53:54","slug":"parallel-processing-and-multithreading","status":"publish","type":"post","link":"https:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/","title":{"rendered":"Parallel Processing and Multithreading"},"content":{"rendered":"
\n

Almost everyone today has a computer with more than 1 core.\u00a0 Those of us who run time-intensive applications, such as simulations, are frustrated in having to wait for results that should be gotten much sooner had all the cores been fully engaged on the task.\u00a0 Many of us have had the experience of looking at Windows Task Manager and seeing just one processor working at 100% and all the other processors doing pretty much nothing.\u00a0 For years I have been wondering whether I would be able to speed up QRS II to use all of those wasted processors.<\/p>\n

About 3 years ago I embarked on a project to do just that.\u00a0 I knew that Windows wasn\u2019t really designed for parallel processing, but I also knew that it could run parallel \u201cthreads\u201d.\u00a0 My compiler, Delphi, has a standard object called TThread that could be used to accomplish a parallel task.\u00a0 TThread is not the easiest programming feature to implement, and the most adventurous people have used it for an occasional background task or two.\u00a0 Could I get TThread to do parallel processing?<\/p>\n

TThread is rather simple in theory.\u00a0 As soon as a TThread object is created (I literally use the \u201ccreate\u201d method in TThread to do this), an object of TThread runs a user-defined method, \u201cexecute\u201d, which contains a task.\u00a0 When the task is done, the TThread object is told to destroy itself.\u00a0 Code within \u201cexecute\u201d can share data arrays and subroutines with the main program, which has considerable advantages.\u00a0 Here is the TThread \u201cexecute\u201d that I use to calculate a gradients (direction of steepest ascent; a gradient is made up of a bunch of partial derivatives) for whole table LS static refinement.<\/p>\n

procedure TTripsQGradThread.Execute;<\/p>\n

var<\/p>\n

found: boolean;<\/p>\n

i, j: integer;<\/p>\n

begin<\/p>\n

for i:= rb to re do<\/p>\n

for j:= rb to re do<\/p>\n

begin<\/p>\n

ThreadCriticalSection.Acquire;<\/p>\n

found:= TripsToDoList[i,j];<\/p>\n

if found then<\/p>\n

begin<\/p>\n

TripsToDoList[i, j]:= false;<\/p>\n

ThreadCriticalSection.Release;<\/p>\n

tripsgradhold[i, j]:= tgradientq(i, j);<\/p>\n

end<\/p>\n

else<\/p>\n

ThreadCriticalSection.Release;<\/p>\n

end;<\/p>\n

Terminate;<\/p>\n

end;<\/p>\n

 <\/p>\n

TTripsQGradThread is a descendent (that is, as customized variation) of the stock TThread. In this code, rb is the lowest zone number and re is the highest zone number.\u00a0 The thread appears to be moving through every possible OD pair and storing the calculated partial derivatives in an array called tripsgradhold.\u00a0 If this were the only thread running, it would calculate all the needed partial derivatives.\u00a0 However, it is not the only thread running.\u00a0 This thread is acting greedily in competition with all the other threads that are running.\u00a0 There is an array, TripsToDoList, that keeps track of which derivatives have been claimed by the various threads.\u00a0 The thread registers its claim before<\/em> it starts the calculation so that no other thread can come along and attempt to do the same thing.<\/p>\n

All code running in a thread must be \u201cthread safe\u201d.\u00a0 That is, the thread must not change any values that may be needed at the same time by any other thread or the main program.\u00a0\u00a0 This rule obviously applies to \u201cexecute\u201d, but it also applies to any subroutine that \u201cexecute\u201d might initiate, such as tgradientq and its subroutines.\u00a0 Threads do not need to be entirely self-contained, but they cannot share any variables or working arrays with other threads.\u00a0 Unfortunately, the TripsToDoList is a working array that must be shared.\u00a0 Microsoft anticipated this problem and gave us a work-around in the object TThreadCriticalSection.\u00a0 An instance of TThreadCriticalSection does one and only one thing:\u00a0 it freezes execution of all threads until the current thread gets done with its critical task, in this case updating the TripsToDoList.<\/p>\n

You might ask:\u00a0 Why did you decide not to divide the tasks evenly across all the threads ahead of time?\u00a0 There are two reasons.\u00a0 First, each thread will not necessarily run at the same rate and tasks may vary hugely in how much work is required.\u00a0 If I create exactly as many threads as there are processors, some of those processers may be tied up with other things the computer needs to do and would not run as efficiently.\u00a0 We really don\u2019t want that already busy processor holding up the whole simulation until it finishes with its pre-assigned tasks.<\/p>\n

The threads are like a bunch of pigeons eating a trough of grain.\u00a0 I raised pigeons as a child and I learned that each pigeon has a distinct personality.\u00a0 Some pigeons are more aggressive, some are slower and some are always hungrier.\u00a0 If I didn\u2019t provide enough grain they would consume the whole trough rather quickly, but not every pigeon would consume the same amount.\u00a0 All the birds will remain at the trough until it was clear they would get no more grain.<\/p>\n

When writing threaded code it is important keep tabs on anything that might be inefficient.\u00a0 For example, the number of lines between acquiring and releasing a TThreadCriticalSection must be as small as possible.\u00a0 We don\u2019t want two threads to write to the same file, because we would need to stop the execution of all but one thread at a time to do so, and file writes take a comparatively long time.\u00a0 We certainly do not want many more threads than processors.\u00a0 And we don\u2019t want to create and destroy threads too frequently, because each creation also takes a comparatively long time.<\/p>\n

Had I known all of this in 1986 when I first started writing QRS II, making the whole program run faster would have been a heck of a lot easier.\u00a0 However, there are now sections of QRS II that would be very difficult to untangle without introducing the possibility new bugs in routines that have been working wonderfully for years. \u00a0\u00a0Thus, I focused on those tasks that have become most time consuming in recent years, particularly path building and OD table refinement. \u00a0\u00a0These parts of the software represent between 75% and 95% of the computational effort.\u00a0 The remaining parts of QRS II (with the exception of area calculations for area-spread traffic assignments) run in a single thread.\u00a0 Thus, computation time is approximately:<\/p>\n

Time = a + b\/(number of processors)<\/p>\n

So in an admittedly best case scenario, a run that originally took 100 minutes on a single processor computer would take just:<\/p>\n

Time = 5 + 95\/8 = 16.9 minutes<\/p>\n

on a computer with 8 processors.\u00a0 Theoretically, this relationship should break down as the number of processors increase to the point when thread management overhead becomes noticeable, but I have not seen this point yet in computers with up to 12 processors.<\/p>\n

So what counts as a processor?\u00a0 Intel\u2019s Core i5 and i7 CPUs come with \u201chypertheading\u201d.\u00a0 That is, they are capable of running two threads per core.\u00a0 My laptop computer has an i5 chip with 2 cores and 2 threads per core. \u00a0Is this two or four processors?\u00a0 Windows 7 counts this chip as having four processors and my empirical tests confirm it.\u00a0 Multithreaded sections of code in QRS II 8 do indeed run four times faster than the same single-threaded portions of QRS II 7.<\/p>\n

This is all very nice, but there are three downsides to multithreading.\u00a0 First, QRS II will monopolize all the processing power of its computer.\u00a0 Without some fiddling, you won\u2019t be able to do even the simplest of other jobs, such as browsing the net, reading e-mail or writing a memo.\u00a0 Even Solitaire will be sticky.\u00a0 Second, QRS II can cause your computer to run very hot.\u00a0 You may not want to run QRS II in your office on a hot summer day if you don\u2019t have great air conditioning.\u00a0 Third, separate working arrays for each thread can gobble up memory.<\/p>\n

I have three suggestions if the computer becomes too hot or two unmanageable.\u00a0 One, keep your simulations on one computer and do all of your other tasks on a second computer.\u00a0 If this cannot be done, then (two) downgrade the number of threads QRS II is allowed to spawn.\u00a0 You can find this setting on the Run Controls dialog box.\u00a0 Third, decrease QRS II\u2019s priority in Windows\u2019 Task Manager.\u00a0 You can safely ignore any warning about terrible things happening if you change QRS II\u2019s priority.<\/p>\n

For your next computer, buy the fastest multicore, multithreaded, Windows-based computer you can find.\u00a0 Don\u2019t settle for some lame computer that has been preselected for you by your IT department.\u00a0 I would look seriously at computers built specifically for gamers, such as Alienware.\u00a0 And, you did not hear it from me, some computers permit overclocking that can boost speed even further.\u00a0 However, keep in mind that overclocking can void your warrantee and possibly fry a $1200 CPU chip if you are too aggressive with your settings. As for the amount of RAM, QRS II is still a 32-bit application and cannot use more than 4 GB under Windows 7. So at this time 6 GB should be enough to handle any QRS II run and a reasonable number of background tasks. Theoretically, a memory bottleneck can form that can slow down QRS II (I have not actually seen this yet), so I suggest installing the fastest RAM available.<\/p>\n

When running QRS II 8 you will notice some subtle and not so subtle differences from QRS II 7. QRS II 8 creates many more temporary files because of the need to keep data from all threads separate, although the total amount of hard drive space is similar. When QRS II shows which path it is building, it skips some centroid numbers. QRS II skips numbers because specifically-created threads cannot update QRS II\u2019s main window, so updates only occur when the main thread (which is also doing its own path building) gets a chance to perform the update. The centroid number that is displayed at any moment is the highest that any thread is currently working on.<\/p>\n

Alan Horowitz, March 27, 2011<\/em><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Almost everyone today has a computer with more than 1 core.\u00a0 Those of us who run time-intensive applications, such as simulations, are frustrated in having to wait for results that should be gotten much sooner had all the cores been fully engaged on the task.\u00a0 Many of us have had the experience of looking at …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"enabled":false},"version":2}},"categories":[8],"tags":[],"class_list":["post-125","post","type-post","status-publish","format-standard","category-qrs-ii-development","anons"],"yoast_head":"\nParallel Processing and Multithreading - QRS II Page<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Parallel Processing and Multithreading - QRS II Page\" \/>\n<meta property=\"og:description\" content=\"Almost everyone today has a computer with more than 1 core.\u00a0 Those of us who run time-intensive applications, such as simulations, are frustrated in having to wait for results that should be gotten much sooner had all the cores been fully engaged on the task.\u00a0 Many of us have had the experience of looking at ...\" \/>\n<meta property=\"og:url\" content=\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/\" \/>\n<meta property=\"og:site_name\" content=\"QRS II Page\" \/>\n<meta property=\"article:published_time\" content=\"2011-03-27T00:00:07+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2017-05-17T01:53:54+00:00\" \/>\n<meta name=\"author\" content=\"horowitz\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"horowitz\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"8 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/#article\",\"isPartOf\":{\"@id\":\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/\"},\"author\":{\"name\":\"horowitz\",\"@id\":\"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070\"},\"headline\":\"Parallel Processing and Multithreading\",\"datePublished\":\"2011-03-27T00:00:07+00:00\",\"dateModified\":\"2017-05-17T01:53:54+00:00\",\"mainEntityOfPage\":{\"@id\":\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/\"},\"wordCount\":1621,\"commentCount\":0,\"articleSection\":[\"QRS II Development\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/\",\"url\":\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/\",\"name\":\"Parallel Processing and Multithreading - QRS II Page\",\"isPartOf\":{\"@id\":\"https:\/\/ajhassoc.com\/#website\"},\"datePublished\":\"2011-03-27T00:00:07+00:00\",\"dateModified\":\"2017-05-17T01:53:54+00:00\",\"author\":{\"@id\":\"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070\"},\"breadcrumb\":{\"@id\":\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/ajhassoc.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Parallel Processing and Multithreading\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/ajhassoc.com\/#website\",\"url\":\"https:\/\/ajhassoc.com\/\",\"name\":\"QRS II Page\",\"description\":\"Information about the travel forecasting package, Quick Response System II\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/ajhassoc.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070\",\"name\":\"horowitz\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g\",\"caption\":\"horowitz\"},\"url\":\"https:\/\/ajhassoc.com\/index.php\/author\/horowitz\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Parallel Processing and Multithreading - QRS II Page","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/","og_locale":"en_US","og_type":"article","og_title":"Parallel Processing and Multithreading - QRS II Page","og_description":"Almost everyone today has a computer with more than 1 core.\u00a0 Those of us who run time-intensive applications, such as simulations, are frustrated in having to wait for results that should be gotten much sooner had all the cores been fully engaged on the task.\u00a0 Many of us have had the experience of looking at ...","og_url":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/","og_site_name":"QRS II Page","article_published_time":"2011-03-27T00:00:07+00:00","article_modified_time":"2017-05-17T01:53:54+00:00","author":"horowitz","twitter_card":"summary_large_image","twitter_misc":{"Written by":"horowitz","Est. reading time":"8 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/#article","isPartOf":{"@id":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/"},"author":{"name":"horowitz","@id":"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070"},"headline":"Parallel Processing and Multithreading","datePublished":"2011-03-27T00:00:07+00:00","dateModified":"2017-05-17T01:53:54+00:00","mainEntityOfPage":{"@id":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/"},"wordCount":1621,"commentCount":0,"articleSection":["QRS II Development"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/#respond"]}]},{"@type":"WebPage","@id":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/","url":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/","name":"Parallel Processing and Multithreading - QRS II Page","isPartOf":{"@id":"https:\/\/ajhassoc.com\/#website"},"datePublished":"2011-03-27T00:00:07+00:00","dateModified":"2017-05-17T01:53:54+00:00","author":{"@id":"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070"},"breadcrumb":{"@id":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/"]}]},{"@type":"BreadcrumbList","@id":"http:\/\/ajhassoc.com\/index.php\/2011\/03\/27\/parallel-processing-and-multithreading\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/ajhassoc.com\/"},{"@type":"ListItem","position":2,"name":"Parallel Processing and Multithreading"}]},{"@type":"WebSite","@id":"https:\/\/ajhassoc.com\/#website","url":"https:\/\/ajhassoc.com\/","name":"QRS II Page","description":"Information about the travel forecasting package, Quick Response System II","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/ajhassoc.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070","name":"horowitz","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g","caption":"horowitz"},"url":"https:\/\/ajhassoc.com\/index.php\/author\/horowitz\/"}]}},"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8zKPW-21","_links":{"self":[{"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/posts\/125","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/comments?post=125"}],"version-history":[{"count":1,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/posts\/125\/revisions"}],"predecessor-version":[{"id":126,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/posts\/125\/revisions\/126"}],"wp:attachment":[{"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/media?parent=125"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/categories?post=125"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/tags?post=125"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}