1 //============================================================================ 2 // Copyright (c) Kitware, Inc. 3 // All rights reserved. 4 // See LICENSE.txt for details. 5 // 6 // This software is distributed WITHOUT ANY WARRANTY; without even 7 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 8 // PURPOSE. See the above copyright notice for more information. 9 //============================================================================ 10 // Copyright (c) 2018, The Regents of the University of California, through 11 // Lawrence Berkeley National Laboratory (subject to receipt of any required approvals 12 // from the U.S. Dept. of Energy). All rights reserved. 13 // 14 // Redistribution and use in source and binary forms, with or without modification, 15 // are permitted provided that the following conditions are met: 16 // 17 // (1) Redistributions of source code must retain the above copyright notice, this 18 // list of conditions and the following disclaimer. 19 // 20 // (2) Redistributions in binary form must reproduce the above copyright notice, 21 // this list of conditions and the following disclaimer in the documentation 22 // and/or other materials provided with the distribution. 23 // 24 // (3) Neither the name of the University of California, Lawrence Berkeley National 25 // Laboratory, U.S. Dept. of Energy nor the names of its contributors may be 26 // used to endorse or promote products derived from this software without 27 // specific prior written permission. 28 // 29 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 30 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 31 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 32 // IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 33 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 34 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 36 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 37 // OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 38 // OF THE POSSIBILITY OF SUCH DAMAGE. 39 // 40 //============================================================================= 41 // 42 // This code is an extension of the algorithm presented in the paper: 43 // Parallel Peak Pruning for Scalable SMP Contour Tree Computation. 44 // Hamish Carr, Gunther Weber, Christopher Sewell, and James Ahrens. 45 // Proceedings of the IEEE Symposium on Large Data Analysis and Visualization 46 // (LDAV), October 2016, Baltimore, Maryland. 47 // 48 // The PPP2 algorithm and software were jointly developed by 49 // Hamish Carr (University of Leeds), Gunther H. Weber (LBNL), and 50 // Oliver Ruebel (LBNL) 51 //============================================================================== 52 53 #ifndef vtk_m_worklet_contourtree_distributed_multiblockcontourtreehelper_h 54 #define vtk_m_worklet_contourtree_distributed_multiblockcontourtreehelper_h 55 56 #include <vtkm/worklet/contourtree_distributed/SpatialDecomposition.h> 57 58 #include <vtkm/worklet/contourtree_augmented/Types.h> 59 #include <vtkm/worklet/contourtree_augmented/meshtypes/ContourTreeMesh.h> 60 61 #include <vtkm/Types.h> 62 #include <vtkm/cont/BoundsCompute.h> 63 #include <vtkm/cont/BoundsGlobalCompute.h> 64 //#include <vtkm/cont/AssignerPartitionedDataSet.h> 65 #include <vtkm/cont/ErrorFilterExecution.h> 66 #include <vtkm/cont/PartitionedDataSet.h> 67 #include <vtkm/worklet/contourtree_augmented/data_set_mesh/IdRelabeler.h> 68 69 namespace vtkm 70 { 71 namespace worklet 72 { 73 namespace contourtree_distributed 74 { 75 76 //--- Helper class to help with the contstuction of the GlobalContourTree 77 class MultiBlockContourTreeHelper 78 { 79 public: 80 VTKM_CONT MultiBlockContourTreeHelper(vtkm::Id3 blocksPerDim,vtkm::Id3 globalSize,const vtkm::cont::ArrayHandle<vtkm::Id3> & localBlockIndices,const vtkm::cont::ArrayHandle<vtkm::Id3> & localBlockOrigins,const vtkm::cont::ArrayHandle<vtkm::Id3> & localBlockSizes)81 MultiBlockContourTreeHelper(vtkm::Id3 blocksPerDim, 82 vtkm::Id3 globalSize, 83 const vtkm::cont::ArrayHandle<vtkm::Id3>& localBlockIndices, 84 const vtkm::cont::ArrayHandle<vtkm::Id3>& localBlockOrigins, 85 const vtkm::cont::ArrayHandle<vtkm::Id3>& localBlockSizes) 86 : MultiBlockSpatialDecomposition(blocksPerDim, 87 globalSize, 88 localBlockIndices, 89 localBlockOrigins, 90 localBlockSizes) 91 { 92 vtkm::Id localNumBlocks = this->GetLocalNumberOfBlocks(); 93 LocalContourTrees.resize(static_cast<std::size_t>(localNumBlocks)); 94 LocalSortOrders.resize(static_cast<std::size_t>(localNumBlocks)); 95 } 96 97 VTKM_CONT ~MultiBlockContourTreeHelper(void)98 ~MultiBlockContourTreeHelper(void) 99 { 100 // FIXME: This shouldn't be necessary as arrays will get deleted anyway 101 LocalContourTrees.clear(); 102 LocalSortOrders.clear(); 103 } 104 GetGlobalBounds(const vtkm::cont::PartitionedDataSet & input)105 inline static vtkm::Bounds GetGlobalBounds(const vtkm::cont::PartitionedDataSet& input) 106 { 107 // Get the spatial bounds of a multi -block data set 108 vtkm::Bounds bounds = vtkm::cont::BoundsGlobalCompute(input); 109 return bounds; 110 } 111 GetLocalBounds(const vtkm::cont::PartitionedDataSet & input)112 inline static vtkm::Bounds GetLocalBounds(const vtkm::cont::PartitionedDataSet& input) 113 { 114 // Get the spatial bounds of a multi -block data set 115 vtkm::Bounds bounds = vtkm::cont::BoundsCompute(input); 116 return bounds; 117 } 118 GetLocalNumberOfBlocks()119 inline vtkm::Id GetLocalNumberOfBlocks() const 120 { 121 return this->MultiBlockSpatialDecomposition.GetLocalNumberOfBlocks(); 122 } 123 GetGlobalNumberOfBlocks()124 inline vtkm::Id GetGlobalNumberOfBlocks() const 125 { 126 return this->MultiBlockSpatialDecomposition.GetGlobalNumberOfBlocks(); 127 } 128 GetGlobalNumberOfBlocks(const vtkm::cont::PartitionedDataSet & input)129 inline static vtkm::Id GetGlobalNumberOfBlocks(const vtkm::cont::PartitionedDataSet& input) 130 { 131 auto comm = vtkm::cont::EnvironmentTracker::GetCommunicator(); 132 vtkm::Id localSize = input.GetNumberOfPartitions(); 133 vtkm::Id globalSize = 0; 134 #ifdef VTKM_ENABLE_MPI 135 vtkmdiy::mpi::all_reduce(comm, localSize, globalSize, std::plus<vtkm::Id>{}); 136 #else 137 globalSize = localSize; 138 #endif 139 return globalSize; 140 } 141 142 // Used to compute the local contour tree mesh in after DoExecute. I.e., the function is 143 // used in PostExecute to construct the initial set of local ContourTreeMesh blocks for 144 // DIY. Subsequent construction of updated ContourTreeMeshes is handled separately. 145 template <typename T> 146 inline static vtkm::worklet::contourtree_augmented::ContourTreeMesh<T>* ComputeLocalContourTreeMesh(const vtkm::Id3 localBlockOrigin,const vtkm::Id3 localBlockSize,const vtkm::Id3 globalSize,const vtkm::cont::ArrayHandle<T> & field,const vtkm::worklet::contourtree_augmented::ContourTree & contourTree,const vtkm::worklet::contourtree_augmented::IdArrayType & sortOrder,unsigned int computeRegularStructure)147 ComputeLocalContourTreeMesh(const vtkm::Id3 localBlockOrigin, 148 const vtkm::Id3 localBlockSize, 149 const vtkm::Id3 globalSize, 150 const vtkm::cont::ArrayHandle<T>& field, 151 const vtkm::worklet::contourtree_augmented::ContourTree& contourTree, 152 const vtkm::worklet::contourtree_augmented::IdArrayType& sortOrder, 153 unsigned int computeRegularStructure) 154 155 { 156 // compute the global mesh index and initalize the local contour tree mesh 157 if (computeRegularStructure == 1) 158 { 159 // Compute the global mesh index 160 vtkm::worklet::contourtree_augmented::IdArrayType localGlobalMeshIndex; 161 auto transformedIndex = vtkm::cont::ArrayHandleTransform< 162 vtkm::worklet::contourtree_augmented::IdArrayType, 163 vtkm::worklet::contourtree_augmented::mesh_dem::IdRelabeler>( 164 sortOrder, 165 vtkm::worklet::contourtree_augmented::mesh_dem::IdRelabeler( 166 localBlockOrigin, localBlockSize, globalSize)); 167 vtkm::cont::Algorithm::Copy(transformedIndex, localGlobalMeshIndex); 168 // Compute the local contour tree mesh 169 auto localContourTreeMesh = new vtkm::worklet::contourtree_augmented::ContourTreeMesh<T>( 170 contourTree.Arcs, sortOrder, field, localGlobalMeshIndex); 171 return localContourTreeMesh; 172 } 173 else if (computeRegularStructure == 2) 174 { 175 // Compute the global mesh index for the partially augmented contour tree. I.e., here we 176 // don't need the global mesh index for all nodes, but only for the augmented nodes from the 177 // tree. We, hence, permute the sortOrder by contourTree.augmentednodes and then compute the 178 // GlobalMeshIndex by tranforming those indices with our IdRelabler 179 vtkm::worklet::contourtree_augmented::IdArrayType localGlobalMeshIndex; 180 vtkm::cont::ArrayHandlePermutation<vtkm::worklet::contourtree_augmented::IdArrayType, 181 vtkm::worklet::contourtree_augmented::IdArrayType> 182 permutedSortOrder(contourTree.Augmentnodes, sortOrder); 183 auto transformedIndex = vtkm::cont::make_ArrayHandleTransform( 184 permutedSortOrder, 185 vtkm::worklet::contourtree_augmented::mesh_dem::IdRelabeler( 186 localBlockOrigin, localBlockSize, globalSize)); 187 vtkm::cont::Algorithm::Copy(transformedIndex, localGlobalMeshIndex); 188 // Compute the local contour tree mesh 189 auto localContourTreeMesh = new vtkm::worklet::contourtree_augmented::ContourTreeMesh<T>( 190 contourTree.Augmentnodes, contourTree.Augmentarcs, sortOrder, field, localGlobalMeshIndex); 191 return localContourTreeMesh; 192 } 193 else 194 { 195 // We should not be able to get here 196 throw vtkm::cont::ErrorFilterExecution( 197 "Parallel contour tree requires at least parial boundary augmentation"); 198 } 199 } 200 201 SpatialDecomposition MultiBlockSpatialDecomposition; 202 std::vector<vtkm::worklet::contourtree_augmented::ContourTree> LocalContourTrees; 203 std::vector<vtkm::worklet::contourtree_augmented::IdArrayType> LocalSortOrders; 204 }; // end MultiBlockContourTreeHelper 205 206 } // namespace contourtree_distributed 207 } // namespace worklet 208 } // namespace vtkm 209 210 #endif 211