Load balancing

 

Load balancing in PPM comprises two main components: domain decomposition and assignment of sub-domains onto processors. While the former has to ensure sufficient granularity and partitioning of the computational cost, the latter has to ensure even distribution of computational load among processors, accounting for possible differences in processor speeds.

Domain decomposition

In order to account for a large spectrum of possible applications, PPM provides a number of different adaptive domain decomposition techniques for particles, meshes, and volumes, the latter defining geometric sub-domains with neither meshes nor particles present. These decompositions currently include:

 

  • recursive orthogonal bisection
  • x-, y-, and z-pencils
  • xy-, xz-, and yz-slabs
  • cuboids
  • user-defined decomposition
  • null decomposition

 

Recursive orthogonal bisection is based on an adaptive binary tree, where subdivisions are allowed in all spatial directions.

Special decompositions

The user-defined decomposition allows the client program to explicitly specify the sub-domains.

The null decomposition does not perform any domain decomposition. It creates only one sub-domain which is the computational domain itself. This trivial decomposition is used to evenly distribute the particles among processors, irrespective of their spatial location. The resulting special topology is called the ring topology and the sub-domain is assigned to every processor.

Processor assignment

The computational cost for each sub-domain (e.g. given by the number of particles, number of mesh points, or the true computational cost) is known from the domain decomposition step. The individual processor speeds are measured using PPM routines. This involves performing a molecular dynamics test simulation of a small Lennard-Jones system using an increasing number of particles until all processors yield sufficient timing statistics. Such speed measurements are important in inhomogeneous machine clusters or under concurrent use of shared processors and typically take less than 1 second of wall-clock time.

Using the computational costs of the sub-domains and the relative processor speeds, PPM provides several methods of assigning the sub-domains to the processors. The PPM-internal method assigns contiguous blocks of sub-domains to processors until the accumulated cost of a processor is greater or equal to the theoretical average cost under uniform load distribution. The average is weighted with the relative processor speeds. In addition, four different Metis-based and a user-defined assignment are available. In conjunction with a user-defined domain decomposition, the user-defined assignment scheme allows the client program to enforce a specific processor affiliation for each sub-domain. For a Metis-assignment, the sub-domain partitioning problem is first translated to the equivalent graph partitioning problem. Two different conversions are supported by \metis: in the primal scheme each sub-domain is represented by a node in the graph and the neighborhood relations by the edges of the graph; the dual scheme represents sub-domains by graph edges. Graph partitioning is then performed such as to minimize either edge cut or communication volume. The relative processor speeds and computational costs of the sub-domains are accounted for by means of weights assigned to the nodes and edges of the graph.

 

 

 

Profile Information

Application afterLoad: 0.000 seconds, 0.28 MB
Application afterInitialise: 0.012 seconds, 0.93 MB
Application afterRoute: 0.016 seconds, 1.23 MB
Application afterDispatch: 0.025 seconds, 1.85 MB
Application afterRender: 0.033 seconds, 2.01 MB

Memory Usage

2140656

12 queries logged

  1. SELECT *
      FROM jos_session
      WHERE session_id = 'bukbbbnkb8vb42q7hhqqm87v27'
  2. DELETE
      FROM jos_session
      WHERE ( time < '1638035157' )
  3. SELECT *
      FROM jos_session
      WHERE session_id = 'bukbbbnkb8vb42q7hhqqm87v27'
  4. INSERT INTO `jos_session` ( `session_id`,`time`,`username`,`gid`,`guest`,`client_id` )
      VALUES ( 'bukbbbnkb8vb42q7hhqqm87v27','1638036057','','0','1','0' )
  5. SELECT *
      FROM jos_components
      WHERE parent = 0
  6. SELECT folder AS type, element AS name, params
      FROM jos_plugins
      WHERE published >= 1
      AND access <= 0
      ORDER BY ordering
  7. SELECT m.*, c.`option` AS component
      FROM jos_menu AS m
      LEFT JOIN jos_components AS c
      ON m.componentid = c.id
      WHERE m.published = 1
      ORDER BY m.sublevel, m.parent, m.ordering
  8. SELECT template
      FROM jos_templates_menu
      WHERE client_id = 0
      AND (menuid = 0 OR menuid = 65)
      ORDER BY menuid DESC
      LIMIT 0, 1
  9. SELECT a.*, u.name AS author, u.usertype, cc.title AS category, s.title AS section, CASE WHEN CHAR_LENGTH(a.alias) THEN CONCAT_WS(":", a.id, a.alias) ELSE a.id END AS slug, CASE WHEN CHAR_LENGTH(cc.alias) THEN CONCAT_WS(":", cc.id, cc.alias) ELSE cc.id END AS catslug, g.name AS groups, s.published AS sec_pub, cc.published AS cat_pub, s.access AS sec_access, cc.access AS cat_access 
      FROM jos_content AS a
      LEFT JOIN jos_categories AS cc
      ON cc.id = a.catid
      LEFT JOIN jos_sections AS s
      ON s.id = cc.section
      AND s.scope = "content"
      LEFT JOIN jos_users AS u
      ON u.id = a.created_by
      LEFT JOIN jos_groups AS g
      ON a.access = g.id
      WHERE a.id = 54
      AND (  ( a.created_by = 0 )    OR  ( a.state = 1
      AND ( a.publish_up = '0000-00-00 00:00:00' OR a.publish_up <= '2021-11-27 18:00:57' )
      AND ( a.publish_down = '0000-00-00 00:00:00' OR a.publish_down >= '2021-11-27 18:00:57' )   )    OR  ( a.state = -1 )  )
  10. UPDATE jos_content
      SET hits = ( hits + 1 )
      WHERE id='54'
  11. SELECT id, title, module, position, content, showtitle, control, params
      FROM jos_modules AS m
      LEFT JOIN jos_modules_menu AS mm
      ON mm.moduleid = m.id
      WHERE m.published = 1
      AND m.access <= 0
      AND m.client_id = 0
      AND ( mm.menuid = 65 OR mm.menuid = 0 )
      ORDER BY position, ordering
  12. SELECT a.*, CASE WHEN CHAR_LENGTH(a.alias) THEN CONCAT_WS(":", a.id, a.alias) ELSE a.id END AS slug, CASE WHEN CHAR_LENGTH(cc.alias) THEN CONCAT_WS(":", cc.id, cc.alias) ELSE cc.id END AS catslug
      FROM jos_content AS a
      INNER JOIN jos_categories AS cc
      ON cc.id = a.catid
      INNER JOIN jos_sections AS s
      ON s.id = a.sectionid
      WHERE a.state = 1 
      AND a.access <= 0
      AND cc.access <= 0
      AND s.access <= 0
      AND (a.publish_up = '0000-00-00 00:00:00' OR a.publish_up <= '2021-11-27 18:00:57' ) 
      AND (a.publish_down = '0000-00-00 00:00:00' OR a.publish_down >= '2021-11-27 18:00:57' )
      AND cc.id = 1
      AND cc.section = s.id
      AND cc.published = 1
      AND s.published = 1
      ORDER BY a.ordering
      LIMIT 0, 4

Language Files Loaded

Untranslated Strings Diagnostic

None

Untranslated Strings Designer

None