Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] View of /branches/vis15/src/compiler/target-cpu/fragments/seq-sarr-dual-indirect.in
ViewVC logotype

View of /branches/vis15/src/compiler/target-cpu/fragments/seq-sarr-dual-indirect.in

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5061 - (download) (annotate)
Fri Jul 14 11:41:14 2017 UTC (2 years, 2 months ago) by jhr
File size: 14814 byte(s)
fix typo in code fragment
// forward declarations of strand methods
#ifdef DIDEROT_HAS_START_METHOD
static diderot::strand_status @STRAND@_start (@START_PARAMS@
    @STRAND@_local *selfLocal, @STRAND@_shared *selfIn, @STRAND@_shared *selfOut);
#endif // DIDEROT_HAS_START_METHOD
static diderot::strand_status @STRAND@_update (@UPDATE_PARAMS@
    @STRAND@_local *selfLocal, @STRAND@_shared *selfIn, @STRAND@_shared *selfOut);
#ifdef DIDEROT_HAS_STABILIZE_METHOD
static void @STRAND@_stabilize (@STABILIZE_PARAMS@
    @STRAND@_local *selfLocal, @STRAND@_shared *selfIn, @STRAND@_shared *selfOut);
#endif // DIDEROT_HAS_STABILIZE_METHOD

// strand_array for BSP/DUAL STATE/INDIRECT ACCESS
//
struct strand_array {
    typedef @STRANDTY@ strand_t;
    typedef uint32_t index_t;           // strand index (index into _idx and _status arrays)
    typedef uint32_t sid_t;             // strand ID (index into strand-state storage)
    typedef char *block_t;              // points to array of @STRANDTY@ structs

    uint8_t             *_status;       // the array of status information for the strands
    uint32_t            *_idx;          // array of strand indices for indirect state rep.
    std::vector<block_t> _blocks;       // vector of pointers to strand-storage blocks
    uint32_t            _inIdx;         // index of shared input state (either 0 or 1)
    uint32_t            _nItems;        // number of items in the _blocks and _status arrays
    uint32_t            _nStable;       // stable strands (in locations 0.._nStable-1)
    uint32_t            _nActive;       // active strands (in locations _nStable.._nStable+_nActive-1)
    uint32_t            _nStabilizing;  // number of stablizing strands
    uint32_t            _nDying;        // number of dying strands
    uint32_t            _nNew;          // number of new strands
    uint32_t            _nFresh;        // number of fresh strands (new strands from previous step)

    static const uint32_t LOG_BLKSZ = 12;               // 2^12 items per block
    static const uint32_t BLKSZ = (1 << LOG_BLKSZ);
    static const uint32_t BLKMASK = (BLKSZ-1);          // mask for block index

    strand_array () : _status(nullptr), _idx(nullptr), _nItems(0) { }
    ~strand_array ();

    uint32_t in_state_index () const { return this->_inIdx; }

    uint32_t num_active () const { return this->_nActive; }
    uint32_t num_stable () const { return this->_nStable; }
    uint32_t num_alive () const { return this->_nActive+this->_nStable; }
    uint32_t num_fresh () const { return this->_nFresh; }

  // return the ID of a strand, which is the value of the _idx array
    sid_t id (index_t ix) const
    {
        assert (ix < this->_nItems);
        return this->_idx[ix];
    }
  // return a pointer to the strand with the given ID
    @STRANDTY@ *id_to_strand (sid_t id) const
    {
        assert (id < this->_nItems);
        uint32_t blkId = id >> LOG_BLKSZ;
        uint32_t offset = id & BLKMASK;
        return reinterpret_cast<@STRANDTY@ *>(this->_blocks[blkId] + offset * sizeof(@STRANDTY@));
    }

  // return a strand's status
    diderot::strand_status status (index_t ix) const
    {
        assert (ix < this->_nItems);
        return static_cast<diderot::strand_status>(this->_status[ix]);
    }
  // return a pointer to the given strand
    @STRANDTY@ *strand (index_t ix) const
    {
        return this->id_to_strand(this->id(ix));
    }

  // return a pointer to the local state of strand ix
    @STRAND@_local *local_state (index_t ix) const
    {
        return &(this->strand(ix)->_local);
    }
  // return a pointer to the local state of strand with the given ID
    @STRAND@_local *id_to_local_state (sid_t id) const
    {
        return &(this->id_to_strand(id)->_local);
    }
  // return a pointer to the in-state of strand ix
    const @STRAND@_shared *in_state (index_t ix) const
    {
        return &(this->strand(ix)->_shared[this->_inIdx]);
    }
  // return a pointer to the in-state of the strand with the given ID
    const @STRAND@_shared *id_to_in_state (sid_t id) const
    {
        return &(this->id_to_strand(id)->_shared[this->_inIdx]);
    }
  // return a pointer to the out-state of strand ix
    @STRAND@_shared *out_state (index_t ix) const
    {
        return &(this->strand(ix)->_shared[this->_inIdx ^ 1]);
    }

  // wrappers for accessing the state of newly created strands
    @STRAND@_local *new_local_state (index_t ix) const
    {
        return this->local_state(ix);
    }
    @STRAND@_shared *new_out_state (index_t ix) const
    {
        return this->out_state(ix);
    }

  // is an index valid for the strand array?
    bool validIndex (index_t ix) const { return (ix < this->_nItems); }

  // is a given strand alive?
    bool isAlive (index_t ix) const
    {
#ifdef DIDEROT_HAS_STRAND_DIE
        return aliveSts(this->status(ix));
#else
        return true;
#endif
    }

  // deallocate space reserved for strands
    void dealloc ();

  // allocate space for at least nItems
    bool alloc (uint32_t nItems)
    {
        nItems = (nItems + BLKSZ - 1) & ~BLKMASK;
        uint32_t nBlks = nItems >> LOG_BLKSZ;
      // allocate block vector
        this->_blocks.resize(nBlks, nullptr);
      // allocate blocks
        for (int i = 0;  i < nBlks;  i++) {
            this->_blocks[i] = static_cast<char *>(std::malloc (BLKSZ * sizeof(@STRANDTY@)));
            if (this->_blocks[i]  == nullptr) {
              // unable to allocate memory
                this->dealloc();
                return true;
            }
        }
      // allocate _status array
        this->_status = static_cast<uint8_t *>(std::malloc (nItems * sizeof(uint8_t)));
        if (this->_status == nullptr) {
            this->dealloc();
            return true;
        }
      // allocate _idx array
        this->_idx = static_cast<uint32_t *>(std::malloc (nItems * sizeof(uint32_t)));
        if (this->_idx == nullptr) {
            this->dealloc();
            return true;
        }
      // initialize arrays
        for (index_t ix = 0;  ix < nItems;  ix++) {
            this->_status[ix] = diderot::kDead;
            this->_idx[ix] = ix;
        }
        this->_inIdx = 0;
        this->_nItems = nItems;
        this->_nActive = 0;
        this->_nStable = 0;
        this->_nStabilizing = 0;
        this->_nNew = 0;
        this->_nDying = 0;
        this->_nFresh = 0;
        return false;
    }

  // initialize the first nStrands locations as new active strands
    void create_strands (uint32_t nStrands)
    {
        assert (this->_nActive == 0);
        assert (this->_nItems >= nStrands);
        for (index_t ix = 0;  ix < nStrands;  ix++) {
            this->_status[ix] = diderot::kActive;
            new (this->strand(ix)) @STRANDTY@;
        }
        this->_nActive = nStrands;
        this->_nFresh = nStrands;
    }

  // swap in and out states
    void swap ()
    {
        this->_inIdx ^= 1;
    }

#ifdef DIDEROT_HAS_START_METHOD
  // invoke strand's start method
    diderot::strand_status strand_start (@START_PARAMS@index_t ix)
    {
        @STRANDTY@ *self = this->strand(ix);
        return @STRAND@_start (@START_ARGS@
            &self->_local,
            &self->_shared[this->_inIdx],
            &self->_shared[this->_inIdx^1]);
    }
#endif // DIDEROT_HAS_START_METHOD

  // invoke strand's update method
    diderot::strand_status strand_update (@UPDATE_PARAMS@index_t ix)
    {
        @STRANDTY@ *self = this->strand(ix);
        return @STRAND@_update (@UPDATE_ARGS@
            &self->_local,
            &self->_shared[this->_inIdx],
            &self->_shared[this->_inIdx^1]);
    }

  // invoke strand's stabilize method
    index_t strand_stabilize (@STABILIZE_PARAMS@index_t ix)
    {
        @STRANDTY@ *self = this->strand(ix);
        @STRAND@_shared *selfIn = &self->_shared[this->_inIdx];
        @STRAND@_shared *selfOut = &self->_shared[this->_inIdx^1];
#ifdef DIDEROT_HAS_STABILIZE_METHOD
      // note that we swap out and in here because out holds the current state
        @STRAND@_stabilize (@STABILIZE_ARGS@&self->_local, selfOut, selfIn);
        std::memcpy (selfOut, selfIn, sizeof(@STRAND@_shared));
#else
        std::memcpy (selfIn, selfOut, sizeof(@STRAND@_shared));
#endif // DIDEROT_HAS_STABILIZE_METHOD
      // we swap the strand-indices at ix and _nStable + this->_nStabilizing
        uint32_t jx = this->_nStable + this->_nStabilizing;
        this->_status[jx] = diderot::kStabilize;
        std::swap (this->_idx[ix], this->_idx[jx]);
        this->_nStabilizing++;
        return ix+1;
    }

  // record that the specified strand is dying
    index_t kill (index_t ix)
    {
        assert (this->_nStable <= ix);
        assert (ix < this->num_alive());
        this->_nDying++;
        uint32_t jx = this->num_alive() - this->_nDying;
        this->_status[jx] = diderot::kDie;
        std::swap (this->_idx[ix], this->_idx[jx]);
        return ix;  // don't advance, since ix is an active strand after the swap
    }

  // allocate a new strand
    index_t new_strand ()
    {
        index_t ix = this->num_alive() + this->_nNew;
        if (this->_nItems <= ix) {
            if (this->grow ()) {
                std::cerr << "Fatal error: unable to allocate space for new strands" << std::endl;
                exit (1);
            }
        }
        this->_status[ix] = diderot::kNew;
        new (this->strand(ix)) @STRANDTY@;
        this->_nNew++;
        return ix;
    }

  // finish a step by updating the strand statuses and the various counters
    bool finish_step ()
    {
        bool anyNewDie = ((this->_nDying + this->_nNew) > 0);
        index_t next = this->_nStable;
        for (index_t ix = 0;  ix < this->_nStabilizing;  ix++, next++) {
            this->_status[next] = diderot::kStable;
        }
        if (this->_nDying == 0) {
          // no need to swap strands
            index_t next = this->num_alive();
            for (auto ix = 0;  ix < this->_nNew;  ix++, next++) {
                this->_status[next] = diderot::kActive;
            }
        }
        else {
          // first handle the dying strands
            next = this->num_alive() - this->_nDying;
            for (index_t ix = 0;  ix < this->_nDying;  ix++, next++) {
                this->_status[next] = diderot::kDead;
              // invoke the dead strand's destructors
                reinterpret_cast<@STRANDTY@ *>(this->strand(next))->~@STRANDTY@();
            }
          // move the new strands down over the dying strands
            index_t src = this->num_alive();
            index_t dst = src - this->_nDying;
            for (auto ix = 0;  ix < this->_nNew;  ix++, dst++, src++) {
                this->_status[dst] = diderot::kActive;
                this->_status[src] = diderot::kDead;
                std::swap (this->_idx[src], this->_idx[dst]);
            }
        }

      // update counts
        this->_nFresh = this->_nNew;
        this->_nStable += this->_nStabilizing;
        this->_nActive -= this->_nStabilizing + this->_nDying;
        this->_nActive += this->_nNew;
        this->_nStabilizing = 0;
        this->_nNew = 0;
        this->_nDying = 0;

        return anyNewDie;
    }

  // finish a kill_all operation
    void finish_kill_all ()
    {
        this->_nActive -= this->_nDying;
        this->_nDying = 0;
    }

  // finish a stabilize_all operation
    void finish_stabilize_all ()
    {
        this->_nStable += this->_nStabilizing;
        this->_nActive -= this->_nStabilizing;
        this->_nStabilizing = 0;
    }

  // iterator over stable strands
    index_t begin_stable () const { return 0; }
    index_t end_stable () const { return this->_nStable; }
    index_t next_stable (index_t &ix) const { return ++ix; }

  // iterator over active strands
    index_t begin_active () const { return this->_nStable+this->_nStabilizing; }
    index_t end_active () const { return this->_nStable+this->_nActive-this->_nDying; }
    index_t next_active (index_t &ix) const { return ++ix; }

  // iterator over alive (active+stable) strands; we assume that _nStabilizing and _nNew are 0
    index_t begin_alive () const { return 0; }
    index_t end_alive () const { return this->num_alive(); }
    index_t next_alive (index_t &ix) const { return ++ix; }

  // iterator over fresh strands
    index_t begin_fresh () const { return this->num_alive() - this->_nFresh; }
    index_t end_fresh () const { return this->num_alive(); }
    index_t next_fresh (index_t &ix) const { return ++ix; }

  // allocate more space for strand state; return true on error
    bool grow ()
    {
        size_t nItems = static_cast<size_t>(this->_nItems) + BLKSZ;
        if (nItems >= UINT32_MAX) {
          // cannot have more than UINT32_MAX elements
            return true;
        }

      // allocate a new block at the end of the _blocks array
        char *blk = static_cast<char *>(std::malloc (BLKSZ * sizeof(@STRANDTY@)));
        if (blk == nullptr) {
            return true;
        }
        this->_blocks.push_back (blk);

      // grow the _status and _idx arrays
        uint8_t *status = static_cast<uint8_t *>(std::malloc (nItems * sizeof(uint8_t)));
        uint32_t *idx = static_cast<uint32_t *>(std::malloc (nItems * sizeof(uint32_t)));
        if ((status == nullptr) || (idx == nullptr)) {
            return true;
        }
        std::memcpy (status, this->_status, this->_nItems * sizeof(uint8_t));
        std::memcpy (idx, this->_idx, this->_nItems * sizeof(uint32_t));

      // initialize the new storage
        @STRANDTY@ *p = reinterpret_cast<@STRANDTY@ *>(blk);
        for (uint32_t ix = this->_nItems;  ix < nItems;  ix++) {
            status[ix] = diderot::kDead;
            idx[ix] = ix;
        }

      // free the old storage
        std::free (this->_status);
        std::free (this->_idx);

      // update pointers
        this->_status = status;
        this->_idx = idx;
        this->_nItems = nItems;

        return false;
    }

}; // struct strand_array

strand_array::~strand_array ()
{
  // run destructors to reclaim any dynamic memory attached to the strand state
    for (auto ix = this->begin_alive();  ix != this->end_alive();  ix = this->next_alive(ix)) {
        this->strand(ix)->~@STRANDTY@();
    }
    this->dealloc();
}

void strand_array::dealloc ()
{
    if (this->_status != nullptr) {
        std::free (this->_status);
        this->_status = nullptr;
    }
    if (this->_idx != nullptr) {
        std::free (this->_idx);
        this->_idx = nullptr;
    }
    for (uint32_t i = 0;  i < this->_blocks.size();  i++) {
        if (this->_blocks[i] != nullptr) {
            std::free (this->_blocks[i]);
            this->_blocks[i] = nullptr;
        }
        else {
            break;
        }
    }
}

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0