dist_m4ri.c File Reference

Multithreaded distance calculation and bracketing (dist_m4ri). More...

#include <inttypes.h>
#include <strings.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdatomic.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <sched.h>
#include <math.h>
#include <limits.h>
#include <m4ri/m4ri.h>
#include "mmio.h"
#include "uthash.h"
#include "util_hash.h"
#include "util_m4ri.h"
#include "util_io.h"
#include "dist_m4ri.h"
#include "dist_cc.h"

Include dependency graph for dist_m4ri.c:

Go to the source code of this file.

Classes
struct	cc_hash_slot_t
struct	cc_hash_t
struct	distfork_ctx_t
struct	worker_arg
struct	cc_walk_t
struct	rw_elim_t
struct	rw_pair_t
struct	rw_pairs_ws_t
struct	cc_hash_col_t

Macros
#define	_GNU_SOURCE
#define	CC_SPLIT_MAX_LEVELS   3 /* CC work units: at most 3 fixed levels, B^3 units per start index (cc_round_levels()) */
#define	CC_IDX_BITS   32
#define	CC_LEV_SHIFT   48
#define	CC_SPLIT_UNITS_PER_THREAD   4.0 /* aim at >= 4 work units of the size of the largest one per CC thread */
#define	CC_SPLIT_MIN_WORK
#define	CC_SPLIT_CLAIMS_PER_WORK   1e4 /* at most 10^4 work units per thread-second of predicted work */
#define	CC_SPLIT_CLAIMS_UNKNOWN   65536 /* at most this many work units if the work of the round is not known */
#define	RW_K_MAX   8 /* at most 2^8 rows per table of rw_eliminate() */
#define	RW_NT_MAX   8 /* at most 8 tables, i.e., 64 pivots per pass over the rows */
#define	RW_TUNE_STEPS   4
#define	RW_PAIRS_POLL   65536
#define	CC_SPAWN_INITIAL   4
#define	CC_SPAWN_WORK   2e-3
#define	CC_SPAWN_TIME   5e-3
#define	M3_DEADLINE_FRACTION   0.75 /* with a timeout, a round gets enough CC threads to finish in 3/4 of the time left */
#define	M3_OVERRUN_FACTOR   1.5 /* a round taking 1.5 times (+20 ms) longer than predicted gets all threads */

Typedefs
typedef struct worker_arg	worker_arg_t

Enumerations
enum	{   STOP_NONE = 0 , STOP_BOUNDS , STOP_CC_FOUND , STOP_RW_CONVERGED ,   STOP_RW_STEPS , STOP_TIMEOUT , STOP_CC_DONE , STOP_CC_SLOW ,   STOP_WMIN , STOP_MAXC , STOP_COLLECTED , STOP_DSTOP }

Functions
int	main (int argc, char **argv)

Detailed Description

Multithreaded distance calculation and bracketing (dist_m4ri).

---

The program implements multithreaded distance calculation:

• method=1: Multithreaded Random Window (RW) algorithm (upper bound)
• method=2: Multithreaded Connected Cluster (CC) algorithm (lower bound / exact)
• method=3: Bracketing mode (artillery fork / вилка) dynamically balancing CC and RW threads based on distance estimate (dexp/dest), current bounds [dmin, dmax], RW step count, timeout, and scaling characteristics.

Output to stdout: "dmin dmax rw_steps" where dmin-1 is the maximum cluster size analyzed without success by CC, dmin=dmax if CC actually found a min-weight codeword of this size, dmax is the smallest weight of a codeword found (by RW or CC, or read with finC), or the supplied dmax if smaller, and rw_steps is the number of completed RW steps (0 if CC found a min-weight codeword or if RW did not run in method=2). NOTE: This 3-number output format is incompatible with legacy single-threaded dist_m4ri_old.

Stop target dstop (method=2, 3): the run ends once CC has certified dmin >= dstop, i.e., that there is no codeword of weight < dstop (with outC, after the rounds w = dstop..dstop+dW which collect codewords), unless a lighter codeword has been found (then the search goes on as usual). Unlike dmax, dstop is not an upper bound and is never reported as dmax. E.g., for d = min(dX, dZ) of a CSS code with d <= U known, the sector runs need dstop=U only.

Expert CC options (see --morehelp) restrict the CC search:

• noscan=1 (method=2): a single CC round at w=wmax. Unless the supplied dmin equals wmax, lower weights are not scanned, so a codeword found only sets dmax and dmin is not raised.
• start=a,b,c: clusters are grown only from the listed columns (without the usual restriction to larger column indices); dmin is valid only under a code symmetry which maps every minimum-weight codeword to one containing a listed column.
• cbeg/cend: split runs; dmin only covers codewords whose smallest column is in [cbeg,cend]. A CC codeword gives dmin=dmax only if found in a round where all lower weights have been analyzed (flag cc_exact).

Threads (default: all logical CPUs available to the process): every worker can run CC rounds, while RW runs only on workers 0..rw_threads-1. Thread throttling (unless nothrottle=1) limits the RW workers for large dense matrices (at most 32, within a quarter of the physical memory, see rw_thread_cap()) and by the step count; in method=3 this limits only the RW share, and CC rounds can use all workers. A worker without RW work (RW steps all claimed, RW stopped by min_hits) joins the current CC round. A CC round hands out work units: start columns, or pieces of them if there are few start columns per thread (see cc_pack()). Method 2 starts only a few workers, and the others once a CC round takes longer (see CC_SPAWN_INITIAL).

Codewords (see codeword_add_maybe()): RW and CC add the codewords found to a hash with hit counts, holding the collection window (weight up to min_w + dW with outC or maxC; exported with outC) and a representative set of cov_cws lowest-weight codewords for the QDistRnd-style min_hits stopping criterion. With outC or maxC, RW does not end the run when the bounds coincide (or on wmin); in method=3 with outC, the CC rounds w = d..d+dW then enumerate all codewords to export. At the end (debug&1), non-uniform hit counts are reported (codeword_hit_check()). With irred=1 (the default), only irreducible codewords are recorded, i.e., not the union of a codeword and a disjoint nonzero zero-syndrome vector: the CC codewords are tested by the rank of their columns (cw_irreducible()), and the RW pairs of disjoint circuits are skipped (rw_pairs_step()); single RW candidates are circuits, hence irreducible.

Timing model (method=2, 3): the CC work of a round is measured as the total CC thread time, and the work of the next round is extrapolated with the growth factor of the last two rounds. With a timeout, a CC round predicted not to finish in time on all threads is not started in method=3 while RW runs (once RW has ended, the run ends); in method=2 (and method=3 with steps=0), it is started anyway, as it can still find a codeword of weight w = dmin. In method=3, the RW step time is measured continuously; the round w = dmax-1 (which certifies dmin = dmax) gets all threads, and while RW has not found any codeword, CC rounds w > dexp run only on the threads which cannot run RW. The coordinator never ends CC while RW still runs.

All debugging messages and confinement profile are sent to stderr (see the DBG_* bits in util_io.h): e.g., the reason why the run ended (DBG_SUMMARY, see ctx_stop()), and a periodic status line (DBG_STATUS, see ctx_status()).

author: Leonid Pryadko leoni.nosp@m.d.pr.nosp@m.yadko.nosp@m.@ucr.nosp@m..edu

Definition in file dist_m4ri.c.

Macro Definition Documentation

_GNU_SOURCE

#define _GNU_SOURCE

Definition at line 67 of file dist_m4ri.c.

CC_IDX_BITS

#define CC_IDX_BITS   32

Definition at line 322 of file dist_m4ri.c.

CC_LEV_SHIFT

#define CC_LEV_SHIFT   48

Definition at line 323 of file dist_m4ri.c.

CC_SPAWN_INITIAL

#define CC_SPAWN_INITIAL   4

Definition at line 2452 of file dist_m4ri.c.

Referenced by main().

CC_SPAWN_TIME

#define CC_SPAWN_TIME   5e-3

Definition at line 2454 of file dist_m4ri.c.

CC_SPAWN_WORK

#define CC_SPAWN_WORK   2e-3

Definition at line 2453 of file dist_m4ri.c.

CC_SPLIT_CLAIMS_PER_WORK

#define CC_SPLIT_CLAIMS_PER_WORK   1e4 /* at most 10^4 work units per thread-second of predicted work */

Definition at line 351 of file dist_m4ri.c.

CC_SPLIT_CLAIMS_UNKNOWN

#define CC_SPLIT_CLAIMS_UNKNOWN   65536 /* at most this many work units if the work of the round is not known */

Definition at line 352 of file dist_m4ri.c.

CC_SPLIT_MAX_LEVELS

#define CC_SPLIT_MAX_LEVELS   3 /* CC work units: at most 3 fixed levels, B^3 units per start index (cc_round_levels()) */

Definition at line 161 of file dist_m4ri.c.

Referenced by main().

CC_SPLIT_MIN_WORK

#define CC_SPLIT_MIN_WORK

Value:

                                       1e-3        /* rounds predicted to take < 1 ms on all threads (on the start indices of an
                                       * expert `start` list, if they are fewer): whole start indices */

Definition at line 350 of file dist_m4ri.c.

CC_SPLIT_UNITS_PER_THREAD

#define CC_SPLIT_UNITS_PER_THREAD   4.0 /* aim at >= 4 work units of the size of the largest one per CC thread */

Definition at line 349 of file dist_m4ri.c.

M3_DEADLINE_FRACTION

#define M3_DEADLINE_FRACTION   0.75 /* with a timeout, a round gets enough CC threads to finish in 3/4 of the time left */

Definition at line 2773 of file dist_m4ri.c.

M3_OVERRUN_FACTOR

#define M3_OVERRUN_FACTOR   1.5 /* a round taking 1.5 times (+20 ms) longer than predicted gets all threads */

Definition at line 2774 of file dist_m4ri.c.

RW_K_MAX

#define RW_K_MAX   8 /* at most 2^8 rows per table of rw_eliminate() */

Definition at line 1286 of file dist_m4ri.c.

RW_NT_MAX

#define RW_NT_MAX   8 /* at most 8 tables, i.e., 64 pivots per pass over the rows */

Definition at line 1287 of file dist_m4ri.c.

RW_PAIRS_POLL

#define RW_PAIRS_POLL   65536

Definition at line 1548 of file dist_m4ri.c.

RW_TUNE_STEPS

#define RW_TUNE_STEPS   4

Definition at line 1310 of file dist_m4ri.c.

Typedef Documentation

worker_arg_t

typedef struct worker_arg worker_arg_t

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
STOP_NONE
STOP_BOUNDS
STOP_CC_FOUND
STOP_RW_CONVERGED
STOP_RW_STEPS
STOP_TIMEOUT
STOP_CC_DONE
STOP_CC_SLOW
STOP_WMIN
STOP_MAXC
STOP_COLLECTED
STOP_DSTOP

Definition at line 275 of file dist_m4ri.c.

Function Documentation

main()

int main	(	int	argc,
		char **	argv )

Definition at line 3396 of file dist_m4ri.c.

References CW_VEC_T::arr, distfork_ctx_t::cc_hash, CC_SPAWN_INITIAL, CC_SPLIT_MAX_LEVELS, CW_VEC_T::cnt, CW_VEC_T::cnt_u, CW_VEC_T::cnt_w, codeword_feed_limit(), codeword_hit_check(), csr_all_ones_in_rowspan(), csr_free(), csr_max_row_wght(), csr_transpose(), worker_arg::ctx, DBG_CWDUMP, DBG_PROGRESS, DBG_SUMMARY, DBG_TIMING, distfork_ctx_t::dexp, ERROR, CW_VEC_T::hh, worker_arg::irr_ws, MAX_W, worker_arg::min_swei, mzd_nullspace(), cc_hash_t::ncols, UT_hash_handle::next, cc_hash_t::nkeys, distfork_ctx_t::num_threads, nzlist_read(), nzlist_write(), distfork_ctx_t::p, p, print_codeword_stats(), print_rw_infoset_estimate(), print_rw_step_stats(), prm, distfork_ctx_t::rw_threads, distfork_ctx_t::start_time, STOP_DSTOP, STOP_NONE, worker_arg::tid, distfork_ctx_t::timeout, cc_hash_t::tmask, var_init(), var_kill(), and CW_VEC_T::weight.