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(). On the one hand, the 3n2 CB allocations during
MPI_Init() contend for a single mca_common_sm_mmap->map_seg-
>seg_lock lock. On the other hand, I know so far of no data showing
that this lock contention is impairing 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 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
pass an array of addresses in. These addresses will be assumed to be
allocated and should be used for the CB components.
If the "array of addresses" is NULL, then we 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_addr ) {
fifo->head = cb_addr[1]; /* use supplied 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 addresses to use for CB components rather than having callees
allocate memory for them.
Use such a supplied address, if available, when allocating the FIFO
(not CB) head.
Function: ompi_fifo_init()
Change the call in ompi_fifo_write_to_head() to ompi_cb_fifo_init()
to reflect the new interface, passing NULL as the new argument.
• 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. At large
n, however, 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().
Regarding the 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: should be eliminated
More accurate sizing could help reduce the problems users see
starting sm jobs with large on-node-process counts.
One problem is that the size of the shared file is set by mpool_sm,
but information about how much shared memory needs to be allocated
during MPI_Init() is in btl_sm. Since OMPI doesn't easily allow
components to call one another, we're stuck.
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.
It would be nice to size the mmap file automatically better than
what is done today, but (as noted) I haven't yet figured out how to
make the btl_sm and mpool_sm components talk to each other.
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?
_______________________________________________
devel mailing list
de...@open-mpi.org
http://www.open-mpi.org/mailman/listinfo.cgi/devel
