Open MPI logo

Open MPI Development Mailing List Archives

  |   Home   |   Support   |   FAQ   |   all Development mailing list

Subject: [OMPI devel] RFC: Fragmented sm Allocations
From: Eugene Loh (Eugene.Loh_at_[hidden])
Date: 2009-01-15 01:54:47


I put back more code changes and refreshed the RFC a little. So, if you
want a latest/greatest copy, here is the (slightly) amended RFC. Thanks
for the positive feedback so far, but more scrutiny is appreciated!


RFC: Fragmented sm Allocations

RFC: Fragmented sm Allocations

WHAT: Dealing with the fragmented allocations of sm BTL FIFO circular buffers (CB) during MPI_Init().

Also:

  • Improve handling of error codes.
  • Automate the sizing of the mmap file.

WHY: To reduce consumption of shared memory, making job startup more robust, and possibly improving the scalability of startup.

WHERE: In mca_btl_sm_add_procs(), there is a loop over calls to ompi_fifo_init(). This is where CBs are initialized one at a time, components of a CB allocated individually. Changes can be seen in ssh://www.open-mpi.org/~eugene/hg/sm-allocation.

WHEN: Upon acceptance.

TIMEOUT: January 30, 2009.


WHY (details)

The sm BTL establishes a FIFO for each non-self, on-node connection. Each FIFO is initialized during MPI_Init() with a circular buffer (CB). (More CBs can be added later in program execution if a FIFO runs out of room.)

A CB has different components that are used in different ways:

  • The "wrapper" is read by both sender and receiver, but is rarely written.
  • The "queue" (FIFO entries) is accessed by both the sender and receiver.
  • The "head" is accessed by the sender.
  • The "tail" is accessed by the receiver.

For performance reasons, a CB is not allocated as one large data structure. Rather, these components are laid out separately in memory and the wrapper has pointers to the various locations. Performance considerations include:

  • false sharing: a component used by one process should not share a cacheline with another component that is modified by another process
  • NUMA: certain components should perhaps be mapped preferentially to memory pages that are close to the processes that access these components

Currently, the sm BTL handles these issues by allocating each component of each CB its own page. (Actually, it couples tails and queues together.)

As the number of on-node processes grows, however, the shared-memory allocation skyrockets. E.g., let's say there are n processes on-node. There are therefore n(n-1) = O(n2) FIFOs, each with 3 allocations (wrapper, head, and tail/queue). The shared-memory allocation for CBs becomes 3n2 pages. For large n, this dominates the shared-memory consumption, even though most of the CB allocation is unused. E.g., a 12-byte "head" ends up consuming a full memory page!

Not only is the 3n2-page allocation large, but it is also not tunable via any MCA parameters.

Large shared-memory consumption has led to some number of start-up and other user problems. E.g., the e-mail thread at http://www.open-mpi.org/community/lists/devel/2008/11/4882.php.

WHAT (details)

Several actions are recommended here.

1. Cacheline Rather than Pagesize Alignment

The first set of changes reduces pagesize to cacheline alignment. Though mapping to pages is motivated by NUMA locality, note:

  • The code already has NUMA locality optimizations (maffinity and mpools) anyhow.
  • There is no data that I'm aware of substantiating the benefits of locality optimizations in this context.

    More to the point, I've tried some such experiments myself. I had two processes communicating via shared memory on a large SMP that had a large difference between remote and local memory access times. I timed the roundtrip latency for pingpongs between the processes. That time was correlated to the relative separation between the two processes, and not at all to the placement of the physical memory backing the shared variables. It did not matter if the memory was local to the sender or receiver or remote from both! (E.g., colocal processes showed fast timings even if the shared memory were remote to both processes.)

    My results do not prove that all NUMA platforms behave in the same way. My point is only that, though I understand the logic behind locality optimizations for FIFO placement, the only data I am aware of does not substantiate that logic.

The changes are:

  • File: ompi/mca/mpool/sm/mpool_sm_module.c
    Function: mca_mpool_sm_alloc()

    Use the alignment requested by the caller rather than adding additional pagesize alignment as well.

  • File: ompi/class/ompi_fifo.h
    Function: ompi_fifo_init() and ompi_fifo_write_to_head()

    Align ompi_cb_fifo_wrapper_t structure on cacheline rather than page.

  • File: ompi/class/ompi_circular_buffer_fifo.h
    Function: ompi_cb_fifo_init()

    Align the two calls to mpool_alloc on cacheline rather than page.

2. Aggregated Allocation

Another option is to lay out all the CBs at once and aggregate their allocations.

This may have the added benefit of reducing lock contention during MPI_Init(), since the 3n2 CB allocations during MPI_Init() all contend for a single mca_common_sm_mmap->map_seg->seg_lock lock. (To be fair, so far I know of no data showing that this lock contention actually impairs start-up scalability.)

The objectives here would be to consolidate many CB components together subject to:

  • queues should be local to receivers
  • heads should be local to senders
  • tails should be local to receivers
  • wrappers should not share cachelines with heads or tails

In sum, for process myrank, the proposed FIFO allocation in shared memory during MPI_Init() looks something like this:

    ompi_fifo_t   from  0  to myrank
    ompi_fifo_t   from  1  to myrank
    ompi_fifo_t   from  2  to myrank
    ...
    ompi_fifo_t   from n-1 to myrank
    --- cacheline boundary ---
    queue of pointers, for CB from  0  to myrank
    queue of pointers, for CB from  1  to myrank
    queue of pointers, for CB from  2  to myrank
    ...
    queue of pointers, for CB from n-1 to myrank
    --- cacheline boundary ---
    head for CB from myrank to  0
    tail for CB from  0  to myrank
    head for CB from myrank to  1
    tail for CB from  1  to myrank
    head for CB from myrank to  2
    tail for CB from  2  to myrank
    ...
    head for CB from myrank to n-1
    tail for CB from n-1 to myrank
    --- cacheline boundary ---
    wrapper, CB from  0  to myrank
    wrapper, CB from  1  to myrank
    wrapper, CB from  2  to myrank
    ...
    wrapper, CB from n-1 to myrank

Note that out-bound heads and in-bound tails are interwoven. There should be no false sharing, however, even if multiple heads and tails share the same cacheline, since they're all accessed by the same process.

For multi-threaded processes, however, it is conceivable that different threads will be passing many messages to different peers. So, for multi-threaded jobs, we spread heads and tails out onto their own cachelines. Consuming the extra shared memory in the multi-threaded case is probably tolerable since the on-node-process count will be lower.

The changes are:

  • File: ompi/class/ompi_circular_buffer_fifo.h
    Function: ompi_cb_fifo_init()

    Instead of having ompi_cb_fifo_init() allocate each component of a CB separately, change the interface to allow the caller function to supply a pointer to a set of pre-allocated addresses.

    If the caller does not supply pre-allocated addresses, then allocate the CB components as before.

    Here is pseudocode to illustrate this change. We replace

         fifo->head = mpool_alloc(...);   /* allocate head */
         if ( NULL == fifo->head )
             return OMPI_ERR_OUT_OF_RESOURCE;
         
    with
         if ( NULL != cb_addrs ) {
             fifo->head = cb_addrs.head;      /* use pre-allocated address, if available */
         } else {
             fifo->head = mpool_alloc(...);   /* allocate head */
             if ( NULL == fifo->head )
                 return OMPI_ERR_OUT_OF_RESOURCE;
         }
         
  • File: ompi/class/ompi_fifo.h
    Function: ompi_fifo_init()

    Change the interface to ompi_fifo_init() to allow the caller to supply pre-allocated addresses to use for CB components rather than having callees allocate memory for them.

    Use such a pre-allocated address, if supplied, when allocating the FIFO (not CB) head.

    Function: ompi_fifo_write_to_head()

    Change the call in ompi_fifo_write_to_head() to ompi_cb_fifo_init() to reflect the new interface. Since, we will not supply pre-allocated addresses in this case, the additional argument will be NULL.

  • File: ompi/mca/btl/sm/btl_sm.c
    Function: compute_initial_cb_fifo_space() and compute_initial_cb_fifo_addrs()

    Add these two functions to compute how much space will be needed for the aggregated CB allocation and to compute addresses for individual CB components for a particular sender and receiver.

    Function: sm_btl_first_time_init()

    Increase the allocation of FIFOs (call to mpool_calloc) to include room for the CBs.

    Function: mca_btl_sm_add_procs()

    Compute the addresses where CB components should be and pass them into ompi_fifo_init().

These changes impact only the allocation of CBs during MPI_Init(). If FIFOs are grown later during program execution, they will continue to have components allocated in a fragmented manner.

3. Free List Return Codes

This is unrelated to FIFOs, but is related to more robust handling of shared-memory allocation.

The function sm_btl_first_time_init() should test the return values when it allocates free lists. It currently does not test return values, proceeding without a hiccup even if those allocations indicate an error. The proposed change is:

  • File: ompi/mca/btl/sm/btl_sm.c
    Function: sm_btl_first_time_init()

    Test the return codes from the calls to:

         ompi_free_list_init_new()
         ompi_free_list_init_new()
         opal_free_list_init()
         
    returning non-successful error status in case of error.

4. Better Automatic Sizing of mmap File

Currently, the size of the file to be mmaped is governed by three MCA parameters:

  • mpool_sm_max_size
  • mpool_sm_min_size (default 128 Mbytes)
  • mpool_sm_per_peer_size (default 32 Mbytes)

Specifically, the file size is

     min(mpool_sm_max_size,
     max(mpool_sm_min_size,
     n * mpool_sm_per_peer_size))

This file size is a poor approximation for the actual amount of shared memory needed by an application during MPI_Init(). E.g., at n=2, the file is 128M even though less than 1M is needed. Meanwhile, at large n, the file is insufficiently small.

Instead, we should add code that produces a better estimate of how much shared memory will be needed during MPI_Init(). More accurate sizing could help reduce the problems users see starting sm jobs with large on-node-process counts. The sm BTL should generate the desired file size, to be used by the sm mpool in creating the shared memory. Sizing information can be passed from the BTL to the mpool component by adding a size field to the mca_mpool_base_resources_t data structure that is passed.

With improved automatic sizing, we should change these MCA parameters:

  • mpool_sm_max_size: default should be 0 (no limit)
  • mpool_sm_min_size: default should be 0 (no limit)
  • mpool_sm_per_peer_size: parameter should be eliminated

The changes are:

  • File: ompi/mca/mpool/sm/mpool_sm.h
    Declaration: mca_mpool_base_resources_t

    Add a size_t size field to the data structure.

  • File: ompi/mca/btl/sm/btl_sm.c
    Function: sm_btl_first_time_init()

    Determine a reasonable size for the file to mmap into each process for point-to-point shared-memory messages. Set the new res.size field to this value before calling mca_mpool_base_module_create().

  • File: ompi/mca/mpool/sm/mpool_sm_component.c
    Function: mca_mpool_sm_init()

    Instead of setting mca_mpool_sm_component.sm_size "arbitrarily", use the value resources->size passed in by the BTL.

    Function: mca_mpool_sm_init()
    Function: mca_mpool_sm_open()
    Declaration: peer_size_param and default_peer

    Reflect the changes in the MCA "min", "max", and "per-peer" parameters.

  • File: ompi/mca/btl/sm/btl_sm_component.c
    Function: mca_btl_sm_component_open()

    Change the default value of sm_extra_procs from 2 to 0 since no one is taking advantage of this parameter anyhow and reducing it saves space and simplifies addressing and sizing calculations.

Supporting Data

Memory Consumption

Memory consumption can be measured or modeled. (I have a byte-accurate model.)

Here are some comparisons for the case of:

  • 1024 on-node processes
  • 8-byte pointers (LP64 execution model)
  • 4K eager limit
  • 32K chunk size
  • 128-byte cacheline size
  • 4K (Linux) or 8K (Solaris) page size

Here are breakdowns of the shared-memory allocations during MPI_Init() in units of 106 bytes:

                      pagesize alignment   cacheline
                      ------------------   alignment
  description        8K pages   4K pages
  ===============
  CB wrappers           8,682      4,391        235
  CB queues+tails       9,822      5,531      1,374
  CB heads              8,632      4,341        184
  eager freelists       9,171      9,032      8,898
  other                   370        362        355
  ---------------
  total                36,677     23,658     11,046

That is, with pagesize alignment, the CB allocations consume over 3n2 pages and dominate, even though most of that space is unused.

The next biggest contributor is the eager freelists. There are 2n2 eager fragments, each 4K (the eager limit), costing (approximately) 8 Gbytes.

With cacheline alignment:

  • Overall consumption drops by over 2× compared to 4K pages and over 3× compared to 8K pages.
  • The remaining leading category (eager freelists) can now be scaled down by adjusting an existing MCA parameter btl_sm_eager_limit.
  • For that matter, the second leading category (CB queues) can also be scaled down by adjusting an existing MCA parameter btl_sm_size_of_cb_queue.

Here are results when we not only drop from page-size to cacheline alignment, but we also aggregate CB allocations:

  106 bytes          description
  =========          ===============
      1,250          FIFOs and CBs
      8,899          eager freelists
        270          max freelists
     ------          ---------------
     10,418          total

With no more pagesize dependence and little more cacheline dependence, one could really start to shoehorn big jobs into a small shared-memory area. E.g., consider bumping the eager limit down to 256 bytes, the size of a CB queue to 16 entries, and the chunk size to 8K. Then, shared-memory consumption for 1024 processes looks like this:

  106 bytes          description
  =========          ===============
        311          FIFOs and CBs
        544          eager freelists
         68          max freelists
     ------          ---------------
        924          total

Ping-Pong Latency

We can also look at performance. Here are OSU latency results for short messages on a Sun v20z. The absolute numbers are less important than the relative difference between the two sets:

     bytes  before     after

       0      0.85     0.84  µsec
       1      0.97     0.99
       2      0.97     0.98
       4      0.97     0.98
       8      0.97     0.99

There is a penalty for non-null messages due to OMPI "data convertors". Importantly, to within the reproducibility of the measurements, it is unclear if there is any slowdown that one can attribute to the changes. (Results are the median of 5 measurements. The values look smooth, but the error bars, which are difficult to characterize, are probably greater than the 0.01-0.02 µsec differences seen here.)

Other Considerations

Simply going from pagesize alignment to cacheline alignment should be a relatively unintrusive code change and effect most of the reduction in shared-memory allocation.

Also aggregating allocations is more intrusive, but has a few more advantages, including:

  • Slight further reduction in the amount of shared memory allocated.
  • Less lock contention as the number of allocation is reduced from O(n2) to O(n), possibly improving start-up performance.
  • Can provide memory locality even on systems that don't have maffinity support.

My proposed code changes need more testing, especially in the case of multiple memory nodes per node.

It remains unclear to me if error codes are being treated properly in the mca_btl_sm_add_procs() code. E.g., if one process is unable to allocate memory in the shared area, should all processes fail?