tnode.hpp

Go to the documentation of this file.

/*
# =============================================================================
# Copyright (c) 2016 - 2021 Blue Brain Project/EPFL
#
# See top-level LICENSE file for details.
# =============================================================================
*/
 
#pragma once
 
#include <vector>
 
// experiment with ordering strategies for Tree Nodes
#if CORENRN_BUILD
namespace coreneuron {
#else
namespace neuron {
#endif
class TNode;
 
using VecTNode = std::vector<TNode*>;
 
/**
 * \class TNode
 * \brief TNode is the tree node that represents the tree of the compartments
 */
class TNode {
  public:
    TNode(int ix);
    virtual ~TNode();
    TNode* parent;
    VecTNode children;
    size_t mkhash();  /// Hash algorith that generates a hash based on the hash of the children and
                      /// the number of compartments of the children
    size_t hash;      /// Hash value generated by mkhash
    size_t treesize;  /// Total number of compartments from the current node and below
    size_t nodevec_index;   /// index in nodevec that is set in check()
                            /// In cell permute 2 this is set as Breadth First traversal
    size_t treenode_order;  /// For cell permute 1 (Interleaved):
                            /// - This is the id given to the compartments based on a Breadth First
                            /// access on the tree that is created in the original circuit
                            /// - This is what makes the cell ordering interleaved
                            /// For cell permute 2 (Constant Depth):
                            /// VVVTN: Vector (groups of cells) of vector (levels of this group of
                            /// cells. Maxsize = maxlevel) of vector of TNodes This changes 3 times
                            /// during cell permute 2:
                            /// 1. According to the sorting of the nodes of each level
                            /// 2. According to the sorting of the parents' treenode_order of the
                            /// previous ordering
                            /// 3. According to children and parents data races. Parents and
                            /// children of the tree are moved by question2() so that threads that
                            /// exist on the same warp don't have data races when updating the
                            /// children and parent variables, so that threads have to wait in
                            /// atomic instructions. If there are any races then those are solved by
                            /// atomic instructions.
    size_t level;           /// level of of this compartment in the tree
    size_t cellindex;       /// Cell ID that this compartment belongs to
    size_t groupindex;      /// Initialized index / groupsize
    int nodeindex;
};
 
size_t level_from_leaf(VecTNode&);
size_t level_from_root(VecTNode&);
 
/**
 * \brief Implementation of the advanced interleaving strategy (interleave_permute_type == 2)
 *
 * The main steps are the following:
 * 1. warp_balance function creates balanced groups of cells.
 * 2. The compartments/tree nodes populate the groups vector (VVVTN) based on their groupindex and
 * their level (see level_from_root).
 * 3. The analyze() & question2() functions (operating per group) make sure that each cell is still
 * a tree (treenode_order) and that the nodes with same parents belong to separate warps.
 */
void group_order2(VecTNode&, size_t groupsize, size_t ncell);
size_t dist2child(TNode* nd);
 
/**
 * \brief Use of the LPT (Least Processing Time) algorithm to create balanced groups of cells.
 *
 * Competing objectives are to keep identical cells together and also balance warps.
 *
 * \param ncell number of cells
 * \param nodevec vector of compartments from all cells
 * \return number of warps
 */
size_t warp_balance(size_t ncell, VecTNode& nodevec);
 
#define warpsize 32
}  // namespace coreneuron