{"id":24514,"date":"2022-06-03T11:49:03","date_gmt":"2022-06-03T15:49:03","guid":{"rendered":"https:\/\/www.rc.fas.harvard.edu\/?p=24514"},"modified":"2022-06-03T11:56:43","modified_gmt":"2022-06-03T15:56:43","slug":"cluster-fragmentation","status":"publish","type":"post","link":"https:\/\/www.rc.fas.harvard.edu\/blog\/cluster-fragmentation\/","title":{"rendered":"Cluster Fragmentation"},"content":{"rendered":"

by Paul Edmon<\/a> June 3, 2022<\/em><\/p>\n

A common pitfall of High Performance Computing (HPC) scheduling is cluster fragmentation.\u00a0 This is not unique to HPC mind you, any system where you have a limited amount of space that you try to fill with quasi random sized blocks of stuff will end up fragmented at some level (see your last game of Tetris).\u00a0 Within HPC, cluster fragmentation is caused by taking jobs of various shapes and sizes (e.g. core, memory, node, gpu, time) and trying to make sure that everyone gets their required allocation while also ensuring maximum utilization of the resource.<\/p>\n

Initially when you start the problem everything ends up nice and neat.\u00a0 Large jobs end up being stacked together first with smaller jobs used to fill out the gaps.\u00a0 Overtime though the cluster gets more and more fragmented.\u00a0 Jobs exit at random times leading to gaps in the scheduler that are oddly shaped.\u00a0 You cannot put a larger job that has a lot of topology requirements in that space, so the scheduler throws in a smaller job that will fit in that gap.\u00a0 Alternatively a larger job will block of resources as it tries to get its allocation causing many smaller jobs that cannot quite fit to pend.\u00a0 Solving this fragmentation problem is in fact the essence and art of scheduling and the reason why schedulers are nontrivial to write.<\/p>\n

So why is fragmentation such a bad thing? The main issue with fragmentation is that it makes it very hard to schedule jobs that require a lot of structure.\u00a0 Say for example you have a 8 core job.\u00a0 If the job has no structure requirements, the scheduler can give the job one core on a node over here, another couple of cores over there, and cobble together 8 cores worth of compute for the job in fairly short order.\u00a0 However, some jobs need those cores to be put together in a certain way.\u00a0 Maybe the job cannot span multiple nodes and needs all those cores on a single host.\u00a0 Maybe the job needs multiple nodes that are adjacent on the network fabric.\u00a0 If the cluster was not fragmented, finding larger structured blocks like this would be easier and thus jobs of this style would pend for a shorter amount of time.<\/p>\n

Now if all the work for a cluster was of the same style and type, then fragmentation would not happen in the first place.\u00a0 It is the very fact that there is such a diversity of workloads on a HPC cluster that makes fragmentation an issue.\u00a0 You want to be able to serve not just the users submitting lots and lots of small jobs but also the users who want to submit very large well structured jobs, as well as everyone in between (which is frankly most users).\u00a0 Accomplishing this is part of the art of scheduler policy.<\/p>\n

There are three general types of solutions to fragmentation.\u00a0 All have their advantages and disadvantages.\u00a0 The first is to enforce a specific style of job, typically that jobs must occupy at least a complete single node.\u00a0 This moves the atomic size of the job from individual cores to individual nodes.\u00a0 Fragmentation still occurs but it is at the level of nodes and their relation on the network topology.\u00a0 This is a fine solution for MPI workloads which typically want to work in this fashion but not as much for workloads which are smaller than the size of a node.\u00a0 Some codes do not scale well up to a full node or do not even need the full capacity of a node.\u00a0 As such you will end up with nodes being underutilized.\u00a0 The tradeoff then is less fragmentation overall but wasted resources at the individual node level, resources that could have been used if the user had been allowed to declare a more accurate job size.<\/p>\n

The second solution is to privilege larger jobs over smaller jobs or visa versa.\u00a0 This type of scheduling would give priority to jobs that use up more space, mimicking how a person would pack a van to move.\u00a0 The obvious downside is this also means that work those users are doing with the larger jobs is given priority over other work on the cluster.\u00a0 On certain clusters this may be the entire point, after all if you build a giant supercomputer you want to run giant jobs that you cannot run anywhere else.\u00a0 However for a generic research cluster this is not ideal.\u00a0 Size or style of job is not an indicator of the importance of a users work.\u00a0 Lots of small jobs are just as valid as large jobs.\u00a0 You want everyone to get their work done with out preferring one type of job over another.\u00a0 At the end of the day this sort of priority shifting is a philosophical question of what is your cluster for and how it will allocate work to individual users and groups.<\/p>\n

The third solution is to increase the job throughput and decrease the time to defragment.\u00a0 After all the real problem that you are trying to solve is how long a job pends for of any size.\u00a0 The average pending time will be approximately the average time it takes for a job to complete on the cluster, as jobs can only run when free spots open up.\u00a0 This can be done via expansion. However unlike cloud computing, for a variety of reasons HPC clusters cannot usually dynamically expand their resources to meet demand.\u00a0 The other method is to make it so that jobs exit faster.\u00a0 This can be done by setting a maximum time limit for any job.\u00a0 If you set a maximum time limit for a queue of a week then your queue will on average turnover in a week and defragment in a week.\u00a0 If you set it to a day it will do so in a day.\u00a0 Thus you can see that shorter runtimes will solve the pending issue that was caused by the fragmentation by subdividing the time axis of the work.\u00a0 The problem with this is that not all jobs are able to complete in a day or even a week.\u00a0 Many jobs do not have any ability to save their progress and restart.\u00a0 As such you cannot have an arbitrarily short run time but need to pick a time that is amenable to most of the types of jobs your cluster runs.<\/p>\n

As you can see from the three options above there is no silver bullet for solving defragmentation.\u00a0 All have their specific hitches and tradeoffs.\u00a0 Thus a cluster administrator must have an understanding of the community that they are supporting and craft a queue policy that best serves the interest of their users.<\/p>\n","protected":false},"excerpt":{"rendered":"

by Paul Edmon June 3, 2022 A common pitfall of High Performance Computing (HPC) scheduling is cluster fragmentation.\u00a0 This is not unique to HPC mind you, any system where you have a limited amount of space that you try to fill with quasi random sized blocks of stuff will end up fragmented at some level (see your last game of…<\/p>\n

Read more<\/a><\/p>\n","protected":false},"author":126,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[36],"tags":[],"class_list":["post-24514","post","type-post","status-publish","format-standard","hentry","category-blog"],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p42YvN-6no","jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/posts\/24514","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/users\/126"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/comments?post=24514"}],"version-history":[{"count":8,"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/posts\/24514\/revisions"}],"predecessor-version":[{"id":24522,"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/posts\/24514\/revisions\/24522"}],"wp:attachment":[{"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/media?parent=24514"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/categories?post=24514"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rc.fas.harvard.edu\/wp-json\/wp\/v2\/tags?post=24514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}