BioDynaMo  v1.03.58-27764645
uniform_grid_environment.cc
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------
2 //
3 // Copyright (C) 2021 CERN & University of Surrey for the benefit of the
4 // BioDynaMo collaboration. All Rights Reserved.
5 //
6 // Licensed under the Apache License, Version 2.0 (the "License");
7 // you may not use this file except in compliance with the License.
8 //
9 // See the LICENSE file distributed with this work for details.
10 // See the NOTICE file distributed with this work for additional information
11 // regarding copyright ownership.
12 //
13 // -----------------------------------------------------------------------------
14 
16 #include <morton/morton.h> // NOLINT
17 #include "core/algorithm.h"
18 
19 namespace bdm {
20 
21 // -----------------------------------------------------------------------------
24  : grid_(grid) {}
25 
26 // -----------------------------------------------------------------------------
28 
29 // -----------------------------------------------------------------------------
31  if (grid_->total_num_boxes_ == 0) {
32  return;
33  }
34 
35  mo_.Update(grid_->num_boxes_axis_);
36 
37  AllocateMemory();
38  InitializeVectors();
39  InPlaceParallelPrefixSum(cummulated_agents_, grid_->total_num_boxes_);
40 }
41 
42 // -----------------------------------------------------------------------------
44  if (sorted_boxes_.capacity() < grid_->boxes_.size()) {
45  sorted_boxes_.reserve(grid_->boxes_.capacity());
46  }
47  if (cummulated_agents_.capacity() < grid_->boxes_.size()) {
48  cummulated_agents_.reserve(grid_->boxes_.capacity());
49  }
50 }
51 
52 // -----------------------------------------------------------------------------
54 #pragma omp parallel
55  {
56  auto* ti = ThreadInfo::GetInstance();
57  auto num_threads = ti->GetMaxThreads();
58  auto tid = ti->GetMyThreadId();
59  // use static scheduling
60  auto correction = grid_->total_num_boxes_ % num_threads == 0 ? 0 : 1;
61  auto chunk = grid_->total_num_boxes_ / num_threads + correction;
62  auto start = tid * chunk;
63  auto end = std::min(grid_->total_num_boxes_, start + chunk);
64 
65  InitializeVectorFunctor f(grid_, start, sorted_boxes_, cummulated_agents_);
66  mo_.CallMortonIteratorConsumer(start, end - 1, f);
67  }
68 }
69 
70 // -----------------------------------------------------------------------------
71 struct AgentHandleIterator : public Iterator<AgentHandle> {
73  uint64_t start, end, box_index, discard;
76  uint64_t tid;
77 
79  uint64_t end, uint64_t box_index, uint64_t discard,
80  decltype(sorted_boxes) sorted_boxes)
81  : grid_(grid),
82  start(start),
83  end(end),
84  box_index(box_index),
85  discard(discard),
86  sorted_boxes(sorted_boxes),
87  box_it(sorted_boxes[box_index]->begin(grid)) {
88  // discard elements
90  for (uint64_t i = 0; i < discard; ++i) {
91  Next();
92  this->start--;
93  }
94  }
95 
96  bool HasNext() const override { return start < end; }
97 
98  AgentHandle Next() override {
99  while (box_it.IsAtEnd()) {
100  box_index++;
101  box_it = sorted_boxes[box_index]->begin(grid_);
102  }
103  auto ret = *box_it;
104  start++;
105  ++box_it;
106  return ret;
107  }
108 };
109 
110 // -----------------------------------------------------------------------------
111 
114 
115  if (rm->GetNumAgents() != 0) {
116  Clear();
117  timestamp_++;
118 
119  auto* param = Simulation::GetActive()->GetParam();
120  if (determine_sim_size_) {
121  auto inf = Math::kInfinity;
122  std::array<real_t, 6> tmp_dim = {{inf, -inf, inf, -inf, inf, -inf}};
124  RoundOffGridDimensions(tmp_dim);
125  } else {
126  grid_dimensions_[0] = static_cast<int>(floor(param->min_bound));
127  grid_dimensions_[2] = static_cast<int>(floor(param->min_bound));
128  grid_dimensions_[4] = static_cast<int>(floor(param->min_bound));
129  grid_dimensions_[1] = static_cast<int>(ceil(param->max_bound));
130  grid_dimensions_[3] = static_cast<int>(ceil(param->max_bound));
131  grid_dimensions_[5] = static_cast<int>(ceil(param->max_bound));
132  }
133 
134  // If the box_length_ is not set manually, we set it to the largest agent
135  // size
137  auto los = ceil(GetLargestAgentSize());
138  assert(los > 0 &&
139  "The largest object size was found to be 0. Please check if your "
140  "cells are correctly initialized.");
141  box_length_ = los;
142  } else if (!is_custom_box_length_ && !determine_sim_size_) {
143  Log::Fatal("UniformGridEnvironment",
144  "No box length specified although determine_sim_size_ is "
145  "set to false. Call the member function "
146  "SetBoxLength(box_length), or SetDetermineSimSize(false).");
147  }
149 
150  if (!determine_sim_size_) {
153  }
154 
155  for (int i = 0; i < 3; i++) {
156  int dimension_length =
157  grid_dimensions_[2 * i + 1] - grid_dimensions_[2 * i];
158  int r = dimension_length % box_length_;
159  // If the grid is not perfectly divisible along each dimension by the
160  // resolution, extend the grid so that it is
161  if (r != 0) {
162  // std::abs for the case that box_length_ > dimension_length
163  grid_dimensions_[2 * i + 1] += (box_length_ - r);
164  } else {
165  // Else extend the grid dimension with one row, because the outmost
166  // object lies exactly on the border
167  grid_dimensions_[2 * i + 1] += box_length_;
168  }
169  }
170 
171  // Pad the grid to avoid out of bounds check when search neighbors
172  for (int i = 0; i < 3; i++) {
173  grid_dimensions_[2 * i] -= box_length_;
174  grid_dimensions_[2 * i + 1] += box_length_;
175  }
176 
177  // Calculate how many boxes fit along each dimension
178  for (int i = 0; i < 3; i++) {
179  int dimension_length =
180  grid_dimensions_[2 * i + 1] - grid_dimensions_[2 * i];
181  assert((dimension_length % box_length_ == 0) &&
182  "The grid dimensions are not a multiple of its box length");
183  num_boxes_axis_[i] = dimension_length / box_length_;
184  }
185 
188 
189  CheckGridGrowth();
190 
191  // resize boxes_
192  if (boxes_.size() != total_num_boxes_) {
193  if (boxes_.capacity() < total_num_boxes_) {
194  boxes_.reserve(total_num_boxes_ * 2);
195  }
196  boxes_.resize(total_num_boxes_);
197  }
198 
199  successors_.reserve();
200 
201  // Assign agents to boxes
202  AssignToBoxesFunctor functor(this);
203  rm->ForEachAgentParallel(param->scheduling_batch_size, functor);
204  if (param->bound_space) {
205  int min = param->min_bound;
206  int max = param->max_bound;
207  threshold_dimensions_ = {min, max};
208  }
209 
210  if (param->thread_safety_mechanism ==
211  Param::ThreadSafetyMechanism::kAutomatic) {
212  nb_mutex_builder_->Update();
213  }
214  } else {
215  // There are no agents in this simulation
216  auto* param = Simulation::GetActive()->GetParam();
217 
218  bool uninitialized = boxes_.size() == 0;
219  if (uninitialized && param->bound_space) {
220  // Simulation has never had any agents
221  // Initialize grid dimensions with `Param::min_bound` and
222  // `Param::max_bound`
223  // This is required for the DiffusionGrid
224  int min = param->min_bound;
225  int max = param->max_bound;
226  grid_dimensions_ = {min, max, min, max, min, max};
227  threshold_dimensions_ = {min, max};
228  has_grown_ = true;
229  } else if (!uninitialized) {
230  // all agents have been removed in the last iteration
231  // grid state remains the same, but we have to set has_grown_ to false
232  // otherwise the DiffusionGrid will attempt to resize
233  has_grown_ = false;
234  } else {
235  Log::Fatal(
236  "UniformGridEnvironment",
237  "You tried to initialize an empty simulation without bound space. "
238  "Therefore we cannot determine the size of the simulation space. "
239  "Please add agents, or set Param::bound_space, "
240  "Param::min_bound, and Param::max_bound.");
241  }
242  }
243 }
244 
245 // -----------------------------------------------------------------------------
247  uint64_t start, uint64_t end,
248  Functor<void, Iterator<AgentHandle>*>& f) const {
249  if (grid_->total_num_boxes_ == 0 || end <= start) {
250  return;
251  }
252  auto index =
253  BinarySearch(start, cummulated_agents_, 0, grid_->total_num_boxes_ - 1) +
254  1;
255  AgentHandleIterator it(grid_, start, end, index,
256  start - cummulated_agents_[index - 1], sorted_boxes_);
257  f(&it);
258 }
259 
260 // -----------------------------------------------------------------------------
263  decltype(sorted_boxes) sorted_boxes,
264  decltype(cummulated_agents) cummulated_agents)
265  : grid(grid),
266  start(start),
267  sorted_boxes(sorted_boxes),
268  cummulated_agents(cummulated_agents) {}
269 
270 // -----------------------------------------------------------------------------
272  ~InitializeVectorFunctor() = default;
273 
274 // -----------------------------------------------------------------------------
277  while (it->HasNext()) {
278  auto morton_code = it->Next();
279  uint_fast32_t x, y, z;
280  libmorton::morton3D_64_decode(morton_code, x, y, z);
281  auto* box = grid->GetBoxPointer(grid->GetBoxIndex(std::array<uint64_t, 3>{
282  static_cast<uint64_t>(x), static_cast<uint64_t>(y),
283  static_cast<uint64_t>(z)}));
284  sorted_boxes[start] = box;
285  cummulated_agents[start] = box->Size(grid->timestamp_);
286  start++;
287  }
288 }
289 
290 // -----------------------------------------------------------------------------
294 
296  auto* grid = static_cast<UniformGridEnvironment*>(
298  FixedSizeVector<uint64_t, 27> box_indices;
299  grid->GetMooreBoxIndices(&box_indices, box_idx);
300  thread_local GridNeighborMutex* mutex =
301  new GridNeighborMutex(box_indices, this);
302  mutex->SetMutexIndices(box_indices);
303  return mutex;
304 }
305 
306 // -----------------------------------------------------------------------------
308  const Agent& query,
309  void* criteria) {
310  auto idx = query.GetBoxIdx();
311 
312  FixedSizeVector<const Box*, 27> neighbor_boxes;
313  GetMooreBoxes(&neighbor_boxes, idx);
314 
316 
317  NeighborIterator ni(this, neighbor_boxes, timestamp_);
318  const unsigned batch_size = 64;
319  uint64_t size = 0;
320  Agent* agents[batch_size] __attribute__((aligned(64)));
321 
322  auto process_batch = [&]() {
323  for (uint64_t i = 0; i < size; ++i) {
324  functor(agents[i]);
325  }
326  size = 0;
327  };
328 
329  while (!ni.IsAtEnd()) {
330  auto ah = *ni;
331  // increment iterator already here to hide memory latency
332  ++ni;
333  auto* agent = rm->GetAgent(ah);
334  if (agent != &query) {
335  agents[size] = agent;
336  size++;
337  if (size == batch_size) {
338  process_batch();
339  }
340  }
341  }
342  process_batch();
343 }
344 
345 } // namespace bdm
bdm::UniformGridEnvironment::LoadBalanceInfoUG::InitializeVectorFunctor::InitializeVectorFunctor
InitializeVectorFunctor(UniformGridEnvironment *grid, uint64_t start, decltype(sorted_boxes) sorted_boxes, decltype(cummulated_agents) cummulated_agents)
Definition: uniform_grid_environment.cc:262
bdm::UniformGridEnvironment::LoadBalanceInfoUG::InitializeVectors
void InitializeVectors()
Definition: uniform_grid_environment.cc:53
bdm::FixedSizeVector< uint64_t, 27 >
algorithm.h
bdm::AgentHandleIterator::start
uint64_t start
Definition: uniform_grid_environment.cc:73
bdm::UniformGridEnvironment::determine_sim_size_
bool determine_sim_size_
Definition: uniform_grid_environment.h:664
bdm::Environment::largest_object_size_squared_
real_t largest_object_size_squared_
Definition: environment.h:129
bdm::NeighborMutex
Environment::NeighborMutexBuilder::NeighborMutex NeighborMutex
Definition: uniform_grid_environment.cc:291
bdm::UniformGridEnvironment::LoadBalanceInfoUG::Update
void Update()
Definition: uniform_grid_environment.cc:30
bdm::UniformGridEnvironment::NeighborIterator::IsAtEnd
bool IsAtEnd() const
Definition: uniform_grid_environment.h:175
bdm::ThreadInfo::GetInstance
static ThreadInfo * GetInstance()
Definition: thread_info.cc:21
bdm::UniformGridEnvironment::LoadBalanceInfoUG::CallHandleIteratorConsumer
void CallHandleIteratorConsumer(uint64_t start, uint64_t end, Functor< void, Iterator< AgentHandle > * > &f) const override
Definition: uniform_grid_environment.cc:246
bdm
Definition: agent.cc:39
bdm::AgentHandleIterator::sorted_boxes
const ParallelResizeVector< UniformGridEnvironment::Box * > & sorted_boxes
Definition: uniform_grid_environment.cc:74
bdm::UniformGridEnvironment::Box::Size
uint16_t Size(uint64_t grid_timestamp) const
Definition: uniform_grid_environment.h:98
bdm::UniformGridEnvironment::ForEachNeighbor
void ForEachNeighbor(Functor< void, Agent *, real_t > &lambda, const Agent &query, real_t squared_radius) override
Applies the given lambda to each neighbor of the specified agent is within the squared radius.
Definition: uniform_grid_environment.h:402
bdm::Iterator
Definition: iterator.h:21
bdm::UniformGridEnvironment::Box::Iterator
An iterator that iterates over the cells in this box.
Definition: uniform_grid_environment.h:125
bdm::Environment::CalcSimDimensionsAndLargestAgent
void CalcSimDimensionsAndLargestAgent(std::array< real_t, 6 > *ret_grid_dimensions)
Definition: environment.h:193
bdm::UniformGridEnvironment
A class that represents Cartesian 3D grid.
Definition: uniform_grid_environment.h:58
bdm::ParallelResizeVector::begin
iterator begin()
Definition: parallel_resize_vector.h:170
bdm::UniformGridEnvironment::box_length_squared_
int32_t box_length_squared_
Length of a Box squared.
Definition: uniform_grid_environment.h:658
bdm::UniformGridEnvironment::num_boxes_xy_
size_t num_boxes_xy_
Number of boxes in the xy plane (=num_boxes_axis_[0] * num_boxes_axis_[1])
Definition: uniform_grid_environment.h:668
bdm::UniformGridEnvironment::GridNeighborMutexBuilder::GetMutex
NeighborMutex * GetMutex(uint64_t box_idx) override
Definition: uniform_grid_environment.cc:295
bdm::UniformGridEnvironment::GridNeighborMutexBuilder
Definition: uniform_grid_environment.h:536
bdm::AgentHandleIterator
Definition: uniform_grid_environment.cc:71
bdm::ParallelResizeVector
std::vector with parallel resize
Definition: parallel_resize_vector.h:27
bdm::UniformGridEnvironment::boxes_
ParallelResizeVector< Box > boxes_
Definition: uniform_grid_environment.h:651
bdm::UniformGridEnvironment::LoadBalanceInfoUG::LoadBalanceInfoUG
LoadBalanceInfoUG(UniformGridEnvironment *grid)
Definition: uniform_grid_environment.cc:22
bdm::Environment::NeighborMutexBuilder::NeighborMutex
Definition: environment.h:108
bdm::UniformGridEnvironment::NeighborIterator
An iterator that iterates over the boxes in this grid.
Definition: uniform_grid_environment.h:159
bdm::UniformGridEnvironment::LoadBalanceInfoUG::~LoadBalanceInfoUG
virtual ~LoadBalanceInfoUG()
bdm::UniformGridEnvironment::threshold_dimensions_
std::array< int32_t, 2 > threshold_dimensions_
Definition: uniform_grid_environment.h:684
bdm::UniformGridEnvironment::LoadBalanceInfoUG::InitializeVectorFunctor::operator()
void operator()(Iterator< uint64_t > *it) override
Definition: uniform_grid_environment.cc:276
bdm::Environment::has_grown_
bool has_grown_
Definition: environment.h:126
bdm::UniformGridEnvironment::successors_
AgentVector< AgentHandle > successors_
Definition: uniform_grid_environment.h:676
bdm::UniformGridEnvironment::LoadBalanceInfoUG::AllocateMemory
void AllocateMemory()
Definition: uniform_grid_environment.cc:43
bdm::Agent
Contains code required by all agents.
Definition: agent.h:79
bdm::UniformGridEnvironment::GetMooreBoxIndices
void GetMooreBoxIndices(FixedSizeVector< uint64_t, 27 > *box_indices, size_t box_idx) const
Gets the box indices of all adjacent boxes. Also adds the query box index.
Definition: uniform_grid_environment.h:803
uniform_grid_environment.h
bdm::Functor
Definition: functor.h:24
bdm::InPlaceParallelPrefixSum
void InPlaceParallelPrefixSum(T &v, uint64_t n)
Definition: algorithm.h:27
bdm::UniformGridEnvironment::num_boxes_axis_
std::array< uint64_t, 3 > num_boxes_axis_
Stores the number of Boxes for each axis.
Definition: uniform_grid_environment.h:666
bdm::UniformGridEnvironment::grid_dimensions_
std::array< int32_t, 6 > grid_dimensions_
Definition: uniform_grid_environment.h:681
bdm::Math::kInfinity
static constexpr real_t kInfinity
Helpful constant to identify 'infinity'.
Definition: math.h:35
bdm::UniformGridEnvironment::GetBoxIndex
size_t GetBoxIndex(const Real3 &position) const
Return the box index in the one dimensional array of the box that contains the position.
Definition: uniform_grid_environment.h:326
bdm::Simulation::GetResourceManager
ResourceManager * GetResourceManager()
Returns the ResourceManager instance.
Definition: simulation.cc:261
bdm::UniformGridEnvironment::Clear
void Clear() override
Clears the grid.
Definition: uniform_grid_environment.h:239
bdm::AgentHandleIterator::box_it
UniformGridEnvironment::Box::Iterator box_it
Definition: uniform_grid_environment.cc:75
bdm::UniformGridEnvironment::box_length_
int32_t box_length_
Length of a Box.
Definition: uniform_grid_environment.h:656
bdm::GridNeighborMutexBuilder
UniformGridEnvironment::GridNeighborMutexBuilder GridNeighborMutexBuilder
Definition: uniform_grid_environment.cc:293
bdm::UniformGridEnvironment::timestamp_
uint32_t timestamp_
Definition: uniform_grid_environment.h:654
bdm::Log::Fatal
static void Fatal(const std::string &location, const Args &... parts)
Prints fatal error message.
Definition: log.h:115
bdm::Iterator::HasNext
virtual bool HasNext() const =0
bdm::UniformGridEnvironment::LoadBalanceInfoUG::InitializeVectorFunctor
Definition: uniform_grid_environment.h:630
bdm::BinarySearch
uint64_t BinarySearch(const TSearch &search_val, const TContainer &container, uint64_t from, uint64_t to)
Definition: algorithm.h:76
bdm::Agent::GetBoxIdx
uint32_t GetBoxIdx() const
Definition: agent.cc:125
bdm::AgentHandleIterator::AgentHandleIterator
AgentHandleIterator(UniformGridEnvironment *grid, uint64_t start, uint64_t end, uint64_t box_index, uint64_t discard, decltype(sorted_boxes) sorted_boxes)
Definition: uniform_grid_environment.cc:78
bdm::UniformGridEnvironment::is_custom_box_length_
bool is_custom_box_length_
True when the box length was set manually.
Definition: uniform_grid_environment.h:660
bdm::AgentHandleIterator::Next
AgentHandle Next() override
Definition: uniform_grid_environment.cc:98
bdm::UniformGridEnvironment::CheckGridGrowth
void CheckGridGrowth()
Definition: uniform_grid_environment.h:694
bdm::UniformGridEnvironment::RoundOffGridDimensions
void RoundOffGridDimensions(const std::array< real_t, 6 > &grid_dimensions)
Definition: uniform_grid_environment.h:715
bdm::Iterator::Next
virtual T Next()=0
bdm::UniformGridEnvironment::Box::Iterator::IsAtEnd
bool IsAtEnd()
Definition: uniform_grid_environment.h:133
bdm::UniformGridEnvironment::GetBoxPointer
const Box * GetBoxPointer(size_t index) const
Gets the pointer to the box with the given index.
Definition: uniform_grid_environment.h:919
bdm::UniformGridEnvironment::GetMooreBoxes
void GetMooreBoxes(FixedSizeVector< const Box *, 27 > *neighbor_boxes, size_t box_idx) const
Gets the Moore (i.e adjacent) boxes of the query boxAlso adds the query box.
Definition: uniform_grid_environment.h:738
bdm::UniformGridEnvironment::UpdateImplementation
void UpdateImplementation() override
Updates the grid, as agents may have moved, added or deleted.
Definition: uniform_grid_environment.cc:112
bdm::Simulation::GetEnvironment
Environment * GetEnvironment()
Definition: simulation.cc:277
bdm::UniformGridEnvironment::LoadBalanceInfoUG::InitializeVectorFunctor::~InitializeVectorFunctor
virtual ~InitializeVectorFunctor()
bdm::Environment::GetLargestAgentSize
real_t GetLargestAgentSize() const
Return the size of the largest agent.
Definition: environment.h:94
bdm::AgentHandleIterator::HasNext
bool HasNext() const override
Definition: uniform_grid_environment.cc:96
bdm::AgentHandleIterator::grid_
UniformGridEnvironment * grid_
Definition: uniform_grid_environment.cc:72
bdm::UniformGridEnvironment::total_num_boxes_
uint64_t total_num_boxes_
The total number of boxes in the uniform grid.
Definition: uniform_grid_environment.h:670
bdm::Simulation::GetParam
const Param * GetParam() const
Returns the simulation parameters.
Definition: simulation.cc:271
bdm::UniformGridEnvironment::nb_mutex_builder_
std::unique_ptr< GridNeighborMutexBuilder > nb_mutex_builder_
Definition: uniform_grid_environment.h:691
bdm::UniformGridEnvironment::AssignToBoxesFunctor
Definition: uniform_grid_environment.h:253
bdm::Simulation::GetActive
static Simulation * GetActive()
This function returns the currently active Simulation simulation.
Definition: simulation.cc:67
bdm::ThreadInfo::GetMyThreadId
int GetMyThreadId() const
Definition: thread_info.h:39
bdm::UniformGridEnvironment::GridNeighborMutexBuilder::GridNeighborMutex
Definition: uniform_grid_environment.h:541
bdm::AgentHandleIterator::tid
uint64_t tid
Definition: uniform_grid_environment.cc:76
bdm::Environment::largest_object_size_
real_t largest_object_size_
The size of the largest object in the simulation.
Definition: environment.h:128
bdm::AgentHandle
Definition: agent_handle.h:29