From 2fe85c0146d5a515215bf425659d7424a4c895a9 Mon Sep 17 00:00:00 2001 From: ageay Date: Thu, 8 Aug 2013 10:08:34 +0000 Subject: [PATCH] For load balancing on // interpolation - MEDCouplingPointSet::ComputeNbOfInteractionsWithSrcCells - DataArrayDouble::computeNbOfInteractionsWith - DataArrayInt::splitInBalancedSlices --- doc/doxygen/Doxyfile_med_user.in | 2 +- src/INTERP_KERNEL/BBTree.txx | 33 ++++++++ src/MEDCoupling/MEDCouplingMemArray.cxx | 95 ++++++++++++++++++++++ src/MEDCoupling/MEDCouplingMemArray.hxx | 2 + src/MEDCoupling/MEDCouplingPointSet.cxx | 19 +++++ src/MEDCoupling/MEDCouplingPointSet.hxx | 1 + src/MEDCoupling_Swig/MEDCouplingCommon.i | 3 + src/MEDCoupling_Swig/MEDCouplingMemArray.i | 10 +++ 8 files changed, 164 insertions(+), 1 deletion(-) diff --git a/doc/doxygen/Doxyfile_med_user.in b/doc/doxygen/Doxyfile_med_user.in index 92b73ff7b..ca7b61bbd 100644 --- a/doc/doxygen/Doxyfile_med_user.in +++ b/doc/doxygen/Doxyfile_med_user.in @@ -108,7 +108,7 @@ FILE_PATTERNS = InterpKernelDEC.* \ ParaFIELD.* \ MEDCouplingMesh.* \ MEDCouplingUMesh.* \ - MEDCouplingUMeshDesc.* \ + MEDCoupling1GTUMesh.* \ MEDCouplingPointSet.* \ MEDCouplingCMesh.* \ MEDCouplingStructuredMesh.* \ diff --git a/src/INTERP_KERNEL/BBTree.txx b/src/INTERP_KERNEL/BBTree.txx index f977e24e3..212e43d78 100644 --- a/src/INTERP_KERNEL/BBTree.txx +++ b/src/INTERP_KERNEL/BBTree.txx @@ -194,6 +194,39 @@ public: _right->getIntersectingElems(bb,elems); } + /*! + * This method is very close to getIntersectingElems except that it returns number of elems instead of elems themselves. + */ + int getNbOfIntersectingElems(const double* bb) + { + // terminal node : return list of elements intersecting bb + int ret(0); + if (_terminal) + { + for (int i=0; i<_nbelems; i++) + { + const double* const bb_ptr=_bb+_elems[i]*2*dim; + bool intersects = true; + for (int idim=0; idim-_epsilon|| bb_ptr[idim*2+1]-bb[idim*2]<_epsilon) + intersects=false; + } + if (intersects) + ret++; + } + return ret; + } + //non terminal node + double min = bb[(_level%dim)*2]; + double max = bb[(_level%dim)*2+1]; + if (max < _min_right) + return _left->getNbOfIntersectingElems(bb); + if (min> _max_left) + return _right->getNbOfIntersectingElems(bb); + return _left->getNbOfIntersectingElems(bb)+_right->getNbOfIntersectingElems(bb); + } + /*! returns in \a elems the list of elements potentially containing the point pointed to by \a xx \param xx pointer to query point coords diff --git a/src/MEDCoupling/MEDCouplingMemArray.cxx b/src/MEDCoupling/MEDCouplingMemArray.cxx index 43c1d4866..e96490c05 100644 --- a/src/MEDCoupling/MEDCouplingMemArray.cxx +++ b/src/MEDCoupling/MEDCouplingMemArray.cxx @@ -21,6 +21,7 @@ #include "MEDCouplingMemArray.txx" #include "MEDCouplingAutoRefCountObjectPtr.hxx" +#include "BBTree.txx" #include "GenMathFormulae.hxx" #include "InterpKernelExprParser.hxx" @@ -2084,6 +2085,68 @@ DataArrayInt *DataArrayDouble::findClosestTupleId(const DataArrayDouble *other) return ret.retn(); } +/*! + * This method expects that \a this and \a otherBBoxFrmt arrays are bounding box arrays ( as the output of MEDCouplingPointSet::getBoundingBoxForBBTree method ). + * This method will return a DataArrayInt array having the same number of tuples than \a this. This returned array tells for each cell in \a this + * how many bounding boxes in \a otherBBoxFrmt. + * So, this method expects that \a this and \a otherBBoxFrmt have the same number of components. + * + * \param [in] otherBBoxFrmt - It is an array . + * \param [in] eps - the absolute precision of the detection. when eps < 0 the bboxes are enlarged so more interactions are detected. Inversely when > 0 the bboxes are stretched. + * \sa MEDCouplingPointSet::getBoundingBoxForBBTree + * \throw If \a this and \a otherBBoxFrmt have not the same number of components. + * \throw If \a this and \a otherBBoxFrmt number of components is not even (BBox format). + */ +DataArrayInt *DataArrayDouble::computeNbOfInteractionsWith(const DataArrayDouble *otherBBoxFrmt, double eps) const throw(INTERP_KERNEL::Exception) +{ + if(!otherBBoxFrmt) + throw INTERP_KERNEL::Exception("DataArrayDouble::computeNbOfInteractionsWith : input array is NULL !"); + if(!isAllocated() || !otherBBoxFrmt->isAllocated()) + throw INTERP_KERNEL::Exception("DataArrayDouble::computeNbOfInteractionsWith : this and input array must be allocated !"); + int nbOfComp(getNumberOfComponents()),nbOfTuples(getNumberOfTuples()); + if(nbOfComp!=otherBBoxFrmt->getNumberOfComponents()) + { + std::ostringstream oss; oss << "DataArrayDouble::computeNbOfInteractionsWith : this number of components (" << nbOfComp << ") must be equal to the number of components of input array (" << otherBBoxFrmt->getNumberOfComponents() << ") !"; + throw INTERP_KERNEL::Exception(oss.str().c_str()); + } + if(nbOfComp%2!=0) + { + std::ostringstream oss; oss << "DataArrayDouble::computeNbOfInteractionsWith : Number of components (" << nbOfComp << ") is not even ! It should be to be compatible with bbox format !"; + throw INTERP_KERNEL::Exception(oss.str().c_str()); + } + MEDCouplingAutoRefCountObjectPtr ret(DataArrayInt::New()); ret->alloc(nbOfTuples,1); + const double *thisBBPtr(begin()); + int *retPtr(ret->getPointer()); + switch(nbOfComp/2) + { + case 3: + { + BBTree<3,int> bbt(otherBBoxFrmt->begin(),0,0,otherBBoxFrmt->getNumberOfTuples(),eps); + for(int i=0;i bbt(otherBBoxFrmt->begin(),0,0,otherBBoxFrmt->getNumberOfTuples(),eps); + for(int i=0;i bbt(otherBBoxFrmt->begin(),0,0,otherBBoxFrmt->getNumberOfTuples(),eps); + for(int i=0;i DataArrayInt::partitionByDifferentValues(std::vector return ret; } +/*! + * This method split ids in [0, \c this->getNumberOfTuples() ) using \a this array as a field of weight (>=0 each). + * The aim of this method is to return a set of \a nbOfSlices chunk of contiguous ids as balanced as possible. + * + * \param [in] nbOfSlices - number of slices expected. + * \return - a vector having a size equal to \a nbOfSlices giving the start (included) and the stop (excluded) of each chunks. + * + * \sa DataArray::GetSlice + * \throw If \a this is not allocated or not with exactly one component. + * \throw If an element in \a this if < 0. + */ +std::vector< std::pair > DataArrayInt::splitInBalancedSlices(int nbOfSlices) const throw(INTERP_KERNEL::Exception) +{ + if(!isAllocated() || getNumberOfComponents()!=1) + throw INTERP_KERNEL::Exception("DataArrayInt::splitInBalancedSlices : this array should have number of components equal to one and must be allocated !"); + if(nbOfSlices<=0) + throw INTERP_KERNEL::Exception("DataArrayInt::splitInBalancedSlices : number of slices must be >= 1 !"); + int sum(accumulate(0)),nbOfTuples(getNumberOfTuples()); + int sumPerSlc(sum/nbOfSlices),pos(0); + const int *w(begin()); + std::vector< std::pair > ret(nbOfSlices); + for(int i=0;i p(pos,-1); + int locSum(0); + while(locSum& compoIds) throw(INTERP_KERNEL::Exception); MEDCOUPLING_EXPORT void setPartOfValues1(const DataArrayDouble *a, int bgTuples, int endTuples, int stepTuples, int bgComp, int endComp, int stepComp, bool strictCompoCompare=true) throw(INTERP_KERNEL::Exception); MEDCOUPLING_EXPORT void setPartOfValuesSimple1(double a, int bgTuples, int endTuples, int stepTuples, int bgComp, int endComp, int stepComp) throw(INTERP_KERNEL::Exception); @@ -579,6 +580,7 @@ namespace ParaMEDMEM MEDCOUPLING_EXPORT DataArrayInt *duplicateEachTupleNTimes(int nbTimes) const throw(INTERP_KERNEL::Exception); MEDCOUPLING_EXPORT DataArrayInt *getDifferentValues() const throw(INTERP_KERNEL::Exception); MEDCOUPLING_EXPORT std::vector partitionByDifferentValues(std::vector& differentIds) const throw(INTERP_KERNEL::Exception); + MEDCOUPLING_EXPORT std::vector< std::pair > splitInBalancedSlices(int nbOfSlices) const throw(INTERP_KERNEL::Exception); MEDCOUPLING_EXPORT void useArray(const int *array, bool ownership, DeallocType type, int nbOfTuple, int nbOfCompo) throw(INTERP_KERNEL::Exception); MEDCOUPLING_EXPORT void useExternalArrayWithRWAccess(const int *array, int nbOfTuple, int nbOfCompo) throw(INTERP_KERNEL::Exception); template diff --git a/src/MEDCoupling/MEDCouplingPointSet.cxx b/src/MEDCoupling/MEDCouplingPointSet.cxx index 961fb248a..f216276c6 100644 --- a/src/MEDCoupling/MEDCouplingPointSet.cxx +++ b/src/MEDCoupling/MEDCouplingPointSet.cxx @@ -1039,6 +1039,25 @@ void MEDCouplingPointSet::Rotate3DAlg(const double *center, const double *vect, } } +/*! + * This method allows to give for each cell in \a trgMesh, how much it interacts with cells of \a srcMesh. + * The returned array can be seen as a weighted array on the target cells of \a trgMesh input parameter. + * + * \param [in] srcMesh - source mesh + * \param [in] trgMesh - target mesh + * \param [in] eps - precision of the detection + * \return DataArrayInt * - An array that gives for each cell of \a trgMesh, how many cells in \a srcMesh (regarding the precision of detection \a eps) can interacts. + * + * \throw If \a srcMesh and \a trgMesh have not the same space dimension. + */ +DataArrayInt *MEDCouplingPointSet::ComputeNbOfInteractionsWithSrcCells(const MEDCouplingPointSet *srcMesh, const MEDCouplingPointSet *trgMesh, double eps) throw(INTERP_KERNEL::Exception) +{ + if(!srcMesh || !trgMesh) + throw INTERP_KERNEL::Exception("MEDCouplingPointSet::ComputeNbOfInteractionsWithSrcCells : the input meshes must be not NULL !"); + MEDCouplingAutoRefCountObjectPtr sbbox(srcMesh->getBoundingBoxForBBTree()),tbbox(trgMesh->getBoundingBoxForBBTree()); + return tbbox->computeNbOfInteractionsWith(sbbox,eps); +} + /*! * Creates a new MEDCouplingMesh containing a part of cells of \a this mesh. The new * mesh shares a coordinates array with \a this one. The cells to include to the diff --git a/src/MEDCoupling/MEDCouplingPointSet.hxx b/src/MEDCoupling/MEDCouplingPointSet.hxx index 3faefb9b0..00d9a33b5 100644 --- a/src/MEDCoupling/MEDCouplingPointSet.hxx +++ b/src/MEDCoupling/MEDCouplingPointSet.hxx @@ -102,6 +102,7 @@ namespace ParaMEDMEM static MEDCouplingPointSet *BuildInstanceFromMeshType(MEDCouplingMeshType type); static void Rotate2DAlg(const double *center, double angle, int nbNodes, double *coords); static void Rotate3DAlg(const double *center, const double *vect, double angle, int nbNodes, double *coords); + static DataArrayInt *ComputeNbOfInteractionsWithSrcCells(const MEDCouplingPointSet *srcMesh, const MEDCouplingPointSet *trgMesh, double eps) throw(INTERP_KERNEL::Exception); MEDCouplingMesh *buildPart(const int *start, const int *end) const; MEDCouplingMesh *buildPartAndReduceNodes(const int *start, const int *end, DataArrayInt*& arr) const; MEDCouplingMesh *buildPartRange(int beginCellIds, int endCellIds, int stepCellIds) const throw(INTERP_KERNEL::Exception); diff --git a/src/MEDCoupling_Swig/MEDCouplingCommon.i b/src/MEDCoupling_Swig/MEDCouplingCommon.i index 49b1903c4..92bdc3a2a 100644 --- a/src/MEDCoupling_Swig/MEDCouplingCommon.i +++ b/src/MEDCoupling_Swig/MEDCouplingCommon.i @@ -352,6 +352,7 @@ using namespace INTERP_KERNEL; %newobject ParaMEDMEM::DataArrayDouble::fromSpherToCart; %newobject ParaMEDMEM::DataArrayDouble::getDifferentValues; %newobject ParaMEDMEM::DataArrayDouble::findClosestTupleId; +%newobject ParaMEDMEM::DataArrayDouble::computeNbOfInteractionsWith; %newobject ParaMEDMEM::DataArrayDouble::duplicateEachTupleNTimes; %newobject ParaMEDMEM::DataArrayDouble::__neg__; %newobject ParaMEDMEM::DataArrayDouble::__radd__; @@ -395,6 +396,7 @@ using namespace INTERP_KERNEL; %newobject ParaMEDMEM::MEDCouplingPointSet::getCellIdsLyingOnNodes; %newobject ParaMEDMEM::MEDCouplingPointSet::deepCpyConnectivityOnly; %newobject ParaMEDMEM::MEDCouplingPointSet::getBoundingBoxForBBTree; +%newobject ParaMEDMEM::MEDCouplingPointSet::ComputeNbOfInteractionsWithSrcCells; %newobject ParaMEDMEM::MEDCouplingPointSet::__getitem__; %newobject ParaMEDMEM::MEDCouplingUMesh::New; %newobject ParaMEDMEM::MEDCouplingUMesh::getNodalConnectivity; @@ -1151,6 +1153,7 @@ namespace ParaMEDMEM virtual void tryToShareSameCoordsPermute(const MEDCouplingPointSet& other, double epsilon) throw(INTERP_KERNEL::Exception); static DataArrayDouble *MergeNodesArray(const MEDCouplingPointSet *m1, const MEDCouplingPointSet *m2) throw(INTERP_KERNEL::Exception); static MEDCouplingPointSet *BuildInstanceFromMeshType(MEDCouplingMeshType type) throw(INTERP_KERNEL::Exception); + static DataArrayInt *ComputeNbOfInteractionsWithSrcCells(const MEDCouplingPointSet *srcMesh, const MEDCouplingPointSet *trgMesh, double eps) throw(INTERP_KERNEL::Exception); virtual int getNumberOfNodesInCell(int cellId) const throw(INTERP_KERNEL::Exception); virtual MEDCouplingPointSet *buildBoundaryMesh(bool keepCoords) const throw(INTERP_KERNEL::Exception); virtual DataArrayInt *getCellsInBoundingBox(const INTERP_KERNEL::DirectedBoundingBox& bbox, double eps) throw(INTERP_KERNEL::Exception); diff --git a/src/MEDCoupling_Swig/MEDCouplingMemArray.i b/src/MEDCoupling_Swig/MEDCouplingMemArray.i index b86a95d2f..65e159cbb 100644 --- a/src/MEDCoupling_Swig/MEDCouplingMemArray.i +++ b/src/MEDCoupling_Swig/MEDCouplingMemArray.i @@ -346,6 +346,7 @@ namespace ParaMEDMEM DataArrayDouble *duplicateEachTupleNTimes(int nbTimes) const throw(INTERP_KERNEL::Exception); DataArrayDouble *getDifferentValues(double prec, int limitTupleId=-1) const throw(INTERP_KERNEL::Exception); DataArrayInt *findClosestTupleId(const DataArrayDouble *other) const throw(INTERP_KERNEL::Exception); + DataArrayInt *computeNbOfInteractionsWith(const DataArrayDouble *otherBBoxFrmt, double eps) const throw(INTERP_KERNEL::Exception); void setPartOfValues1(const DataArrayDouble *a, int bgTuples, int endTuples, int stepTuples, int bgComp, int endComp, int stepComp, bool strictCompoCompare=true) throw(INTERP_KERNEL::Exception); void setPartOfValuesSimple1(double a, int bgTuples, int endTuples, int stepTuples, int bgComp, int endComp, int stepComp) throw(INTERP_KERNEL::Exception); void setPartOfValuesAdv(const DataArrayDouble *a, const DataArrayInt *tuplesSelec) throw(INTERP_KERNEL::Exception); @@ -2559,6 +2560,15 @@ namespace ParaMEDMEM return self->accumulatePerChunck(bg,bg+sz); } + PyObject *splitInBalancedSlices(int nbOfSlices) const throw(INTERP_KERNEL::Exception) + { + std::vector< std::pair > slcs(self->splitInBalancedSlices(nbOfSlices)); + PyObject *ret=PyList_New(slcs.size()); + for(std::size_t i=0;i