plugins/alpaka/PFClusterECLCC.h

0001 #ifndef RecoParticleFlow_PFClusterProducer_plugins_alpaka_PFClusterECLCC_h
0002 #define RecoParticleFlow_PFClusterProducer_plugins_alpaka_PFClusterECLCC_h
0003
0004 #include "DataFormats/ParticleFlowReco/interface/alpaka/PFRecHitDeviceCollection.h"
0005 #include "HeterogeneousCore/AlpakaInterface/interface/config.h"
0006 #include "HeterogeneousCore/AlpakaInterface/interface/workdivision.h"
0007 #include "RecoParticleFlow/PFClusterProducer/interface/alpaka/PFClusteringEdgeVarsDeviceCollection.h"
0008 #include "RecoParticleFlow/PFClusterProducer/interface/alpaka/PFClusteringVarsDeviceCollection.h"
0009
0010 // The following comment block is required in using the ECL-CC algorithm for topological clustering
0011
0012 /*
0013   ECL-CC code: ECL-CC is a connected components graph algorithm. The CUDA
0014   implementation thereof is quite fast. It operates on graphs stored in
0015   binary CSR format.
0016
0017   Copyright (c) 2017-2020, Texas State University. All rights reserved.
0018
0019   Redistribution and use in source and binary forms, with or without
0020   modification, are permitted provided that the following conditions are met:
0021
0022      * Redistributions of source code must retain the above copyright
0023        notice, this list of conditions and the following disclaimer.
0024      * Redistributions in binary form must reproduce the above copyright
0025        notice, this list of conditions and the following disclaimer in the
0026        documentation and/or other materials provided with the distribution.
0027      * Neither the name of Texas State University nor the names of its
0028        contributors may be used to endorse or promote products derived from
0029        this software without specific prior written permission.
0030
0031   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
0032   ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
0033   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
0034   DISCLAIMED. IN NO EVENT SHALL TEXAS STATE UNIVERSITY BE LIABLE FOR ANY
0035   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
0036   (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
0037   LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
0038   ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0039   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
0040   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0041
0042   Authors: Jayadharini Jaiganesh and Martin Burtscher
0043
0044   URL: The latest version of this code is available at
0045   https://userweb.cs.txstate.edu/~burtscher/research/ECL-CC/.
0046
0047   Publication: This work is described in detail in the following paper.
0048   Jayadharini Jaiganesh and Martin Burtscher. A High-Performance Connected
0049   Components Implementation for GPUs. Proceedings of the 2018 ACM International
0050   Symposium on High-Performance Parallel and Distributed Computing, pp. 92-104.
0051   June 2018.
0052 */
0053
0054 /*
0055  The code is modified for the specific use-case of generating topological clusters
0056  for PFClustering. It is adapted to work with the Alpaka portability library. The
0057  kernels for processing vertices at warp and block level granularity have been
0058  removed since the degree of vertices in our inputs is only ever 8; the number of
0059  neighbors.
0060 */
0061
0062 namespace ALPAKA_ACCELERATOR_NAMESPACE {
0063
0064   /* intermediate pointer jumping */
0065
0066   ALPAKA_FN_ACC inline int representative(const int idx,
0067                                           reco::PFClusteringVarsDeviceCollection::View pfClusteringVars) {
0068     int curr = pfClusteringVars[idx].pfrh_topoId();
0069     if (curr != idx) {
0070       int next, prev = idx;
0071       while (curr > (next = pfClusteringVars[curr].pfrh_topoId())) {
0072         pfClusteringVars[prev].pfrh_topoId() = next;
0073         prev = curr;
0074         curr = next;
0075       }
0076     }
0077     return curr;
0078   }
0079
0080   // Initial step of ECL-CC. Uses ID of first neighbour in edgeList with a smaller ID
0081   class ECLCCInit {
0082   public:
0083     ALPAKA_FN_ACC void operator()(Acc1D const& acc,
0084                                   reco::PFRecHitDeviceCollection::ConstView pfRecHits,
0085                                   reco::PFClusteringVarsDeviceCollection::View pfClusteringVars,
0086                                   reco::PFClusteringEdgeVarsDeviceCollection::View pfClusteringEdgeVars) const {
0087       const int nRH = pfRecHits.size();
0088       for (int v : cms::alpakatools::uniform_elements(acc, nRH)) {
0089         const int beg = pfClusteringEdgeVars[v].pfrh_edgeIdx();
0090         const int end = pfClusteringEdgeVars[v + 1].pfrh_edgeIdx();
0091         int m = v;
0092         int i = beg;
0093         while ((m == v) && (i < end)) {
0094           m = std::min(m, pfClusteringEdgeVars[i].pfrh_edgeList());
0095           i++;
0096         }
0097         pfClusteringVars[v].pfrh_topoId() = m;
0098       }
0099     }
0100   };
0101
0102   // First edge processing kernel of ECL-CC
0103   // Processes vertices
0104   class ECLCCCompute1 {
0105   public:
0106     ALPAKA_FN_ACC void operator()(Acc1D const& acc,
0107                                   reco::PFRecHitDeviceCollection::ConstView pfRecHits,
0108                                   reco::PFClusteringVarsDeviceCollection::View pfClusteringVars,
0109                                   reco::PFClusteringEdgeVarsDeviceCollection::View pfClusteringEdgeVars) const {
0110       const int nRH = pfRecHits.size();
0111
0112       for (int v : cms::alpakatools::uniform_elements(acc, nRH)) {
0113         const int vstat = pfClusteringVars[v].pfrh_topoId();
0114         if (v != vstat) {
0115           const int beg = pfClusteringEdgeVars[v].pfrh_edgeIdx();
0116           const int end = pfClusteringEdgeVars[v + 1].pfrh_edgeIdx();
0117           int vstat = representative(v, pfClusteringVars);
0118           for (int i = beg; i < end; i++) {
0119             const int nli = pfClusteringEdgeVars[i].pfrh_edgeList();
0120             if (v > nli) {
0121               int ostat = representative(nli, pfClusteringVars);
0122               bool repeat;
0123               do {
0124                 repeat = false;
0125                 if (vstat != ostat) {
0126                   int ret;
0127                   if (vstat < ostat) {
0128                     if ((ret = alpaka::atomicCas(acc, &pfClusteringVars[ostat].pfrh_topoId(), ostat, vstat)) != ostat) {
0129                       ostat = ret;
0130                       repeat = true;
0131                     }
0132                   } else {
0133                     if ((ret = alpaka::atomicCas(acc, &pfClusteringVars[vstat].pfrh_topoId(), vstat, ostat)) != vstat) {
0134                       vstat = ret;
0135                       repeat = true;
0136                     }
0137                   }
0138                 }
0139               } while (repeat);
0140             }
0141           }
0142         }
0143       }
0144     }
0145   };
0146
0147   /* link all vertices to sink */
0148   class ECLCCFlatten {
0149   public:
0150     ALPAKA_FN_ACC void operator()(Acc1D const& acc,
0151                                   reco::PFRecHitDeviceCollection::ConstView pfRecHits,
0152                                   reco::PFClusteringVarsDeviceCollection::View pfClusteringVars,
0153                                   reco::PFClusteringEdgeVarsDeviceCollection::View pfClusteringEdgeVars) const {
0154       const int nRH = pfRecHits.size();
0155
0156       for (int v : cms::alpakatools::uniform_elements(acc, nRH)) {
0157         int next, vstat = pfClusteringVars[v].pfrh_topoId();
0158         const int old = vstat;
0159         while (vstat > (next = pfClusteringVars[vstat].pfrh_topoId())) {
0160           vstat = next;
0161         }
0162         if (old != vstat)
0163           pfClusteringVars[v].pfrh_topoId() = vstat;
0164       }
0165     }
0166   };
0167
0168   // ECL-CC ends
0169
0170 }  // namespace ALPAKA_ACCELERATOR_NAMESPACE
0171
0172 #endif