Module caminos_lib::pattern

source ·
Expand description

A Pattern defines the way elements select their destinations.

see new_pattern for documentation on the configuration syntax of predefined patterns.

Modules

  • prelude
    Some things most uses of the pattern module will use.

Structs

  • CartesianCut
    Select a block in source/destination sets to send traffic according to a pattern and the remainder according to another. The uncut_sides parameter define a large block that may be the whole set, otherwise discarding elements from the end. The cut_sides parameter defines a subblock embedded in the former. This defines two sets of nodes: the ones in the subblock and the rest. A pattern can be provided for each of these two sets. It is possible to specify offsets and strides for the subblock.
  • CartesianEmbedding
    Maps from a block into another following the natural embedding, keeping the coordinates of every node. Both block must have the same number of dimensions, and each dimension should be greater at the destination than at the source. This is intended to be used to place several small applications in a larger machine. It can combined with CartesianTransform to be placed at an offset, to set a stride, or others.
  • CartesianFactor
    Interpretate the origin as with cartesian coordinates. Then add each coordinate with a given factor. It uses default f64 as usize, so a small epsilon may be desired. We do not restrict the destination size to be equal to the source size.
  • CartesianFactorDimension
    Interpretate the origin as with cartesian coordinates. Multiply the first coordinate with a given factor and divide it by each dimension size until it is smaller than the dimension size of a dimension.
  • CartesianTransform
    Interpretate the origin as with cartesian coordinates and apply transformations. May permute the dimensions if they have same side. May complement the dimensions. Order of composition is: multiplier, shift, permute, complement, project, randomize, pattern. If you need another order you may compose several of them.
  • Circulant
    The node at an index sends traffic randomly to one of index+g, where g is any of the declared generators. These sums are made modulo the destination size, which is intended to be equal the source size. the induced communication matrix is a Circulant matrix, hence its name.
  • ComponentsPattern
    Divide the topology according to some given link classes, considering the graph components if the other links were removed. Then apply the global_pattern among the components and select randomly inside the destination component. Note that this uses the topology and will cause problems if used as a sub-pattern.
  • Composition
    The pattern resulting of composing a list of patterns. destination=patterns[len-1]( patterns[len-2] ( ... (patterns[1] ( patterns[0]( origin ) )) ) ). The intermediate sizes along the composition can be stated by middle_sizes, otherwise they are set equal to the target_size of the whole.
  • FileMap
    A map read from file. Each node has a unique destination. See RandomPermutation for related matters. The file is read at creation and should contain only lines with pairs source destination.
  • FixedRandom
    Build a random map on initialization, which is then kept constant. Optionally allow self-messages. See RandomPermutation and FileMap.
  • GloballyShufflingDestinations
    It keeps a shuffled list, global for all sources, of destinations to which send. Once all have sent it is rebuilt and shuffled again. Independently of past requests, decisions or origin.
  • GroupShufflingDestinations
    For each group, it keeps a shuffled list of destinations to which send. Once all have sent it is rebuilt and shuffled again. Independently of past requests, decisions or origin.
  • Hotspots
    The destinations are selected from a given pool of servers.
  • Identity
    Just set destination = origin. Mostly to be used inside some meta-patterns.
  • IndependentRegions
    Partition the nodes in independent regions, each with its own pattern. Source and target sizes must be equal.
  • LinearTransform
    Matrix by vector multiplication. Origin is given coordinates as within a block of size source_size. Then the destination coordinate vector is y=Mx, with x being the origin and M the given matrix. This destination vector is converted into an index into a block of size target_size.
  • PatternBuilderArgument
    The argument to a builder function of patterns.
  • Pow
    The pattern resulting of composing a pattern with itself a number of times..
  • ProductPattern
    A pattern given by blocks. The elements are divided by blocks of size block_size. The global_pattern is used to describe the communication among different blocks and the block_pattern to describe the communication inside a block. Seen as a graph, this is the Kronecker product of the block graph with the global graph. Thus the origin a position i in the block j will select the destination at position b(i) in the block g(j), where b(i) is the destination via the block_pattern and g(j) is the destination via the global_pattern.
  • RandomInvolution
    Build a random involution on initialization, which is then kept constant. An involution is a permutation that is a pairing/matching; if a is the destination of b then b is the destination of a. It will panic if given an odd size. See RandomPermutation.
  • RandomMix
    Use either of several patterns, with probability proportional to a weight.
  • RandomPermutation
    Build a random permutation on initialization, which is then kept constant. This allows self-messages; with a reasonable probability of having one. See RandomInvolution and FileMap.
  • RemappedNodes
    Apply some other Pattern over a set of nodes whose indices have been remapped according to a Pattern-given permutation. A source x chooses as destination map(pattern(invmap(x))), where map is the given permutation, invmap its inverse and pattern is the underlying pattern to apply. In other words, if pattern(a)=b, then destination of map(a) is set to map(b). It can be seen as a Composition that manages building the inverse map.
  • RestrictedMiddleUniform
    A pattern in which the destinations are randomly sampled from the destinations for which there are some middle router satisfying some criteria. Note this is only a pattern, the actual packet route does not have to go through such middle router. It has the same implicit concentration scaling as UniformDistance, allowing building a pattern over a multiple of the number of switches.
  • UniformDistance
    Each message gets its destination sampled uniformly at random among the servers attached to neighbour routers. It may build a pattern either of servers or switches, controlled through the switch_level configuration flag. This pattern autoscales if requested a size multiple of the network size.
  • UniformPattern
    Each destination request will be uniform random among all the range 0..size minus the origin. Independently of past requests, decisions or origin. Has an optional configuration argument allow_self, default to false. This can be useful for composed patterns, for example, for a group to send uniformly into another group.

Traits

  • Pattern
    A Pattern describes how a set of entities decides destinations into another set of entities. The entities are initially servers, but after some operators it may mean router, rows/columns, or other groupings. The source and target set may be or not be the same. Or even be of different size. Thus, a Pattern is a generalization of the mathematical concept of function.

Functions