bmsparsevec_parallel.h
Go to the documentation of this file.
#ifndef BMSPARSEVEC_PARALLEL__H__INCLUDED__
#define BMSPARSEVEC_PARALLEL__H__INCLUDED__
/*
Copyright(c) 2020 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/*! \file bmsparsevec_parallel.h
\brief Parallel planner for operations with sparse vectors
*/
#include "bmsparsevec_serial.h"
namespace bm
{
/**
Builder class to prepare a batch of tasks for parallel optimization of
a sparse vector
@ingroup bmtasks
*/
template<typename SVect, typename Lock>
class optimize_plan_builder
{
public:
typedef SVect sparse_vector_type;
typedef Lock lock_type;
typedef typename sparse_vector_type::bvector_type bvector_type;
typedef typename bvector_type::allocator_type allocator_type;
typedef typename bvector_type::optmode optmode_type;
typedef typename sparse_vector_type::statistics sv_statistics_type;
struct task_batch : public bm::task_batch<allocator_type>
{
typedef bm::task_batch<allocator_type> parent_type;
typedef typename parent_type::task_vector_type task_vector_type;
};
/**
Build paralell optimization batch (of tasks) for sparse vector
@param batch - target batch (can be re-used for multiple vectors)
@param sv - sparse vector for optimization
@param opt_mode - optimization mode (see bvector<>::optmode)
@param st - sparse vector statistics to compute with optimization pass (optional)
*/
static
void build_plan(task_batch& batch,
sparse_vector_type& sv,
typename bvector_type::optmode
opt_mode = bvector_type::opt_compress,
typename sparse_vector_type::statistics* st = 0)
{
typename task_batch::task_vector_type& tv = batch.get_task_vector();
auto rsize = sv.get_bmatrix().rows();
tv.reserve(rsize);
if (st)
st->reset();
for (unsigned k = 0; k < rsize; ++k)
{
if (bvector_type* bv = sv.get_bmatrix().get_row(k))
{
bm::task_function_t task([bv, opt_mode, st] (void* /*argp*/) {
typename bvector_type::statistics stbv;
stbv.reset();
BM_DECLARE_TEMP_BLOCK(tb)
bv->optimize(tb, opt_mode, &stbv);
if (st)
{
static lock_type lk;
bm::lock_guard<lock_type> lg(lk);
st->add(stbv);
}
return 0;
});
batch.add(task, 0);
}
} // for
}
};
/**
Parallel plan builder for the XOR filter scanner.
Parallelization principle here is based on makig a task per 64K bit block (task per NP)
@ingroup bmtasks
*/
template<typename BV>
class compute_sim_matrix_plan_builder
{
public:
typedef BV bvector_type;
typedef typename BV::size_type size_type;
typedef typename bvector_type::allocator_type allocator_type;
typedef bm::bv_ref_vector<BV> bv_ref_vector_type;
struct task_batch : public bm::task_batch<allocator_type>
{
typedef bm::task_batch<allocator_type> parent_type;
typedef typename parent_type::task_vector_type task_vector_type;
};
/**
Construct task batch for parallel execution. (Every task is a lambda).
*/
void build_plan(task_batch& batch,
bm::xor_sim_model<BV>& sim_model,
const bv_ref_vector_type& ref_vect,
const bm::xor_sim_params& xs_params)
{
sim_model.bv_blocks.clear(true);
ref_vect.build_nb_digest_and_xor_matrix(sim_model.matr,
sim_model.bv_blocks);
typename bvector_type::size_type nb_count = sim_model.bv_blocks.count();
typename task_batch::task_vector_type& tv = batch.get_task_vector();
tv.reserve(nb_count);
typename xor_sim_model<BV>::matrix_chain_type &sm_matr = sim_model.matr;
typename bvector_type::enumerator en(sim_model.bv_blocks);
for (size_type col = 0; en.valid(); ++en, ++col)
{
size_type nb = *en;
bm::task_function_t task(
[nb, col, &xs_params, &sm_matr, &ref_vect] (void* /*argp*/) {
thread_local bm::xor_scanner<BV> xor_scan;
xor_scan.set_ref_vector(&ref_vect);
xor_scan.sync_nb_vect();
xor_scan.compute_sim_model(sm_matr, nb, col, xs_params);
return 0;
});
batch.add(task, 0);
} // for en
}
};
/**
Parallel plan builder for succinct sparse vector serialization
@sa sparse_vector_serializer
@ingroup bmtasks
*/
template<typename SV>
class sv_serialization_plan_builder
{
public:
typedef SV sparse_vector_type;
typedef typename SV::bvector_type bvector_type;
typedef typename SV::size_type size_type;
typedef typename bvector_type::allocator_type allocator_type;
typedef bm::bv_ref_vector<bvector_type> bv_ref_vector_type;
typedef bm::xor_sim_model<bvector_type> xor_sim_model_type;
struct serialization_params
{
serialization_params()
: sb_bookmarks_(false),
sb_range_(0),
compression_level_(bm::set_compression_default),
bv_ref_ptr_(0), sim_model_ptr_(0)
{}
bool sb_bookmarks_; ///< Bookmarks flag
unsigned sb_range_; ///< Desired bookmarks interval
unsigned compression_level_;
const bv_ref_vector_type* bv_ref_ptr_;
const xor_sim_model_type* sim_model_ptr_;
};
struct task_batch : public bm::task_batch<allocator_type>
{
typedef bm::task_batch<allocator_type> parent_type;
typedef typename parent_type::task_vector_type task_vector_type;
serialization_params s_params;
};
public:
sv_serialization_plan_builder()
{}
void set_bookmarks(bool enable, unsigned bm_interval = 256) BMNOEXCEPT
{ s_params_.sb_bookmarks_ = enable; s_params_.sb_range_ = bm_interval; }
void set_xor_ref(const bv_ref_vector_type* bv_ref_ptr) BMNOEXCEPT
{ s_params_.bv_ref_ptr_ = bv_ref_ptr; }
void set_sim_model(const xor_sim_model_type* sim_model) BMNOEXCEPT
{ s_params_.sim_model_ptr_ = sim_model; }
void build_plan(task_batch& batch,
sparse_vector_serial_layout<SV>& sv_layout,
const sparse_vector_type& sv)
{
typename task_batch::task_vector_type& tv = batch.get_task_vector();
unsigned planes = sv.stored_slices();
tv.reserve(planes + 1); // +1 for finalization task
batch.s_params = s_params_;
for (unsigned i = 0; i < planes; ++i)
{
typename SV::bvector_type_const_ptr bv = sv.get_slice(i);
if (!bv) // empty plane
{
sv_layout.set_plane(i, 0, 0);
continue;
}
unsigned bv_idx = (unsigned)s_params_.bv_ref_ptr_->find_bv(bv);
BM_ASSERT(bv_idx != s_params_.bv_ref_ptr_->not_found());
bm::task_function_t task(
[bv_idx, &sv_layout] (void* /*argp*/) {
//TODO: full implementation
BM_ASSERT(0);
return 0;
});
bm::task_descr& tdescr = tv.add();
tdescr.init(task, (void*)&tdescr);
// tdescr.ret = (void*)&sv_layout;
if (s_params_.bv_ref_ptr_)
{
BM_ASSERT(batch.s_params.sim_model_ptr_);
/*
tdescr.payload0.u32 =
(unsigned)s_params_.bv_ref_ptr_->find_bv(bv);
BM_ASSERT(tdescr.payload0.u32
!= s_params_.bv_ref_ptr_->not_found());
*/
}
else
{
// ref vector not set: see set_xor_ref()
BM_ASSERT(!batch.s_params.sim_model_ptr_);
}
} // for i
// Add barrier task at the end to finalize the compression
bm::task_function_t task_final(
[&sv_layout] (void* /*argp*/) {
//TODO: full implementation
BM_ASSERT(0);
return 0;
});
bm::task_descr& tdescr = tv.add();
tdescr.init(task_final, (void*)&tdescr);
tdescr.flags = bm::task_descr::barrier_ok;
//tdescr.ret = (void*)&sv_layout;
}
protected:
/// Task execution Entry Point
/// @internal
static void* task_run(void* argp)
{
if (!argp)
return 0;
//TODO: full implementation
return 0;
}
static void* task_run_final(void* argp)
{
if (!argp)
return 0;
//TODO: full implementation
return 0;
}
protected:
serialization_params s_params_;
};
} // namespace bm
#endif
BM_DECLARE_TEMP_BLOCK
#define BM_DECLARE_TEMP_BLOCK(x)
Definition bm.h:47
BMNOEXCEPT
#define BMNOEXCEPT
Definition bmdef.h:82
BM_ASSERT
#define BM_ASSERT
Definition bmdef.h:139
bmsparsevec_serial.h
Serialization for sparse_vector<>.
bm::bv_ref_vector
List of reference bit-vectors with their true index associations.
Definition bmxor.h:624
bm::bv_ref_vector::build_nb_digest_and_xor_matrix
bool build_nb_digest_and_xor_matrix(matrix_chain_type &matr, bvector_type &bv_blocks) const
Calculate blocks digest and resize XOR distance matrix based on total number of available blocks.
Definition bmxor.h:759
bm::bvector::enumerator
Constant iterator designed to enumerate "ON" bits.
Definition bm.h:603
bm::bvector::iterator_base::valid
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Definition bm.h:283
bm::bvector::optmode
optmode
Optimization mode Every next level means additional checks (better compression vs time).
Definition bm.h:133
bm::bvector::opt_compress
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition bm.h:137
bm::bvector::size_type
bvector_size_type size_type
Definition bm.h:121
bm::bvector::allocator_type
Alloc allocator_type
Definition bm.h:117
bm::compute_sim_matrix_plan_builder
Parallel plan builder for the XOR filter scanner.
Definition bmsparsevec_parallel.h:104
bm::compute_sim_matrix_plan_builder::size_type
BV::size_type size_type
Definition bmsparsevec_parallel.h:107
bm::compute_sim_matrix_plan_builder::bvector_type
BV bvector_type
Definition bmsparsevec_parallel.h:106
bm::compute_sim_matrix_plan_builder::allocator_type
bvector_type::allocator_type allocator_type
Definition bmsparsevec_parallel.h:108
bm::compute_sim_matrix_plan_builder::bv_ref_vector_type
bm::bv_ref_vector< BV > bv_ref_vector_type
Definition bmsparsevec_parallel.h:109
bm::compute_sim_matrix_plan_builder::build_plan
void build_plan(task_batch &batch, bm::xor_sim_model< BV > &sim_model, const bv_ref_vector_type &ref_vect, const bm::xor_sim_params &xs_params)
Construct task batch for parallel execution.
Definition bmsparsevec_parallel.h:121
bm::lock_guard
Simple scoped lock guard.
Definition bmtask.h:227
bm::optimize_plan_builder
Builder class to prepare a batch of tasks for parallel optimization of a sparse vector.
Definition bmsparsevec_parallel.h:37
bm::optimize_plan_builder::allocator_type
bvector_type::allocator_type allocator_type
Definition bmsparsevec_parallel.h:43
bm::optimize_plan_builder::sv_statistics_type
sparse_vector_type::statistics sv_statistics_type
Definition bmsparsevec_parallel.h:45
bm::optimize_plan_builder::bvector_type
sparse_vector_type::bvector_type bvector_type
Definition bmsparsevec_parallel.h:42
bm::optimize_plan_builder::optmode_type
bvector_type::optmode optmode_type
Definition bmsparsevec_parallel.h:44
bm::optimize_plan_builder::sparse_vector_type
SVect sparse_vector_type
Definition bmsparsevec_parallel.h:39
bm::optimize_plan_builder::build_plan
static void build_plan(task_batch &batch, sparse_vector_type &sv, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector_type::statistics *st=0)
Build paralell optimization batch (of tasks) for sparse vector.
Definition bmsparsevec_parallel.h:61
bm::optimize_plan_builder::lock_type
Lock lock_type
Definition bmsparsevec_parallel.h:40
bm::sv_serialization_plan_builder::set_bookmarks
void set_bookmarks(bool enable, unsigned bm_interval=256) BMNOEXCEPT
Definition bmsparsevec_parallel.h:202
bm::sv_serialization_plan_builder::sv_serialization_plan_builder
sv_serialization_plan_builder()
Definition bmsparsevec_parallel.h:199
bm::sv_serialization_plan_builder::task_run_final
static void * task_run_final(void *argp)
Definition bmsparsevec_parallel.h:287
bm::sv_serialization_plan_builder::set_xor_ref
void set_xor_ref(const bv_ref_vector_type *bv_ref_ptr) BMNOEXCEPT
Definition bmsparsevec_parallel.h:205
bm::sv_serialization_plan_builder::xor_sim_model_type
bm::xor_sim_model< bvector_type > xor_sim_model_type
Definition bmsparsevec_parallel.h:170
bm::sv_serialization_plan_builder::sparse_vector_type
SV sparse_vector_type
Definition bmsparsevec_parallel.h:165
bm::sv_serialization_plan_builder::build_plan
void build_plan(task_batch &batch, sparse_vector_serial_layout< SV > &sv_layout, const sparse_vector_type &sv)
Definition bmsparsevec_parallel.h:212
bm::sv_serialization_plan_builder::bv_ref_vector_type
bm::bv_ref_vector< bvector_type > bv_ref_vector_type
Definition bmsparsevec_parallel.h:169
bm::sv_serialization_plan_builder::size_type
SV::size_type size_type
Definition bmsparsevec_parallel.h:167
bm::sv_serialization_plan_builder::allocator_type
bvector_type::allocator_type allocator_type
Definition bmsparsevec_parallel.h:168
bm::sv_serialization_plan_builder::set_sim_model
void set_sim_model(const xor_sim_model_type *sim_model) BMNOEXCEPT
Definition bmsparsevec_parallel.h:208
bm::sv_serialization_plan_builder::task_run
static void * task_run(void *argp)
Task execution Entry Point.
Definition bmsparsevec_parallel.h:279
bm::sv_serialization_plan_builder::bvector_type
SV::bvector_type bvector_type
Definition bmsparsevec_parallel.h:166
bm::sv_serialization_plan_builder::s_params_
serialization_params s_params_
Definition bmsparsevec_parallel.h:295
bm::task_batch
Basic implementation for collection of tasks for parallel execution.
Definition bmtask.h:140
bm::task_batch::get_task_vector
task_vector_type & get_task_vector() BMNOEXCEPT
Get access to internal task vector.
Definition bmtask.h:168
bm::task_batch::add
void add(task_function_t f, void *argptr)
Definition bmtask.h:172
bm::task_batch< allocator_type >::task_vector_type
std::vector< bm::task_descr > task_vector_type
Definition bmtask.h:146
bm::xor_scanner
XOR scanner to search for complement-similarities in collections of bit-vectors.
Definition bmxor.h:820
bm::xor_scanner::sync_nb_vect
void sync_nb_vect()
Sync TEMP vector size.
Definition bmxor.h:1732
bm::xor_scanner::compute_sim_model
bool compute_sim_model(xor_sim_model< BV > &sim_model, const bv_ref_vector_type &ref_vect, const bm::xor_sim_params &params)
Calculate matrix of best XOR match metrics per block for the attached collection of bit-vectors.
Definition bmxor.h:1440
bm::xor_scanner::set_ref_vector
void set_ref_vector(const bv_ref_vector_type *ref_vect) BMNOEXCEPT
Definition bmxor.h:850
bm::task_function_t
std::function< int(void *)> task_function_t
Typedef for a call-back functional for lambda capture.
Definition bmtask.h:54
bm
Definition bm.h:78
bm::set_compression_default
const unsigned set_compression_default
Default compression level.
Definition bmserial.h:60
bm::bv_statistics::reset
void reset() BMNOEXCEPT
Reset statisctics.
Definition bmfunc.h:94
bm::bvector::statistics
Statistical information about bitset's memory allocation details.
Definition bm.h:125
bm::compute_sim_matrix_plan_builder::task_batch
Definition bmsparsevec_parallel.h:113
bm::compute_sim_matrix_plan_builder::task_batch::task_vector_type
parent_type::task_vector_type task_vector_type
Definition bmsparsevec_parallel.h:115
bm::compute_sim_matrix_plan_builder::task_batch::parent_type
bm::task_batch< allocator_type > parent_type
Definition bmsparsevec_parallel.h:114
bm::optimize_plan_builder::task_batch
Definition bmsparsevec_parallel.h:48
bm::optimize_plan_builder::task_batch::parent_type
bm::task_batch< allocator_type > parent_type
Definition bmsparsevec_parallel.h:49
bm::optimize_plan_builder::task_batch::task_vector_type
parent_type::task_vector_type task_vector_type
Definition bmsparsevec_parallel.h:50
bm::sparse_vector_serial_layout
layout class for serialization buffer structure
Definition bmsparsevec_serial.h:58
bm::sparse_vector_serial_layout::set_plane
void set_plane(unsigned i, unsigned char *ptr, size_t buf_size) BMNOEXCEPT
Set plane output pointer and size.
Definition bmsparsevec_serial.h:97
bm::sv_serialization_plan_builder::serialization_params
Definition bmsparsevec_parallel.h:174
bm::sv_serialization_plan_builder::serialization_params::compression_level_
unsigned compression_level_
Definition bmsparsevec_parallel.h:184
bm::sv_serialization_plan_builder::serialization_params::sim_model_ptr_
const xor_sim_model_type * sim_model_ptr_
Definition bmsparsevec_parallel.h:187
bm::sv_serialization_plan_builder::serialization_params::sb_range_
unsigned sb_range_
Desired bookmarks interval.
Definition bmsparsevec_parallel.h:183
bm::sv_serialization_plan_builder::serialization_params::serialization_params
serialization_params()
Definition bmsparsevec_parallel.h:175
bm::sv_serialization_plan_builder::serialization_params::bv_ref_ptr_
const bv_ref_vector_type * bv_ref_ptr_
Definition bmsparsevec_parallel.h:186
bm::sv_serialization_plan_builder::serialization_params::sb_bookmarks_
bool sb_bookmarks_
Bookmarks flag.
Definition bmsparsevec_parallel.h:182
bm::sv_serialization_plan_builder::task_batch
Definition bmsparsevec_parallel.h:191
bm::sv_serialization_plan_builder::task_batch::parent_type
bm::task_batch< allocator_type > parent_type
Definition bmsparsevec_parallel.h:192
bm::sv_serialization_plan_builder::task_batch::s_params
serialization_params s_params
Definition bmsparsevec_parallel.h:195
bm::sv_serialization_plan_builder::task_batch::task_vector_type
parent_type::task_vector_type task_vector_type
Definition bmsparsevec_parallel.h:193
bm::task_descr
BitMagic task with a captured function.
Definition bmtask.h:62
bm::task_descr::barrier_ok
@ barrier_ok
barrier waits all prev.tasks done without error
Definition bmtask.h:66
bm::task_descr::init
void init(task_function_t f, void *argptr) noexcept
Definition bmtask.h:98
bm::xor_sim_model
XOR similarity model.
Definition bmxor.h:791
bm::xor_sim_model::matrix_chain_type
bm::dynamic_heap_matrix< block_match_chain_type, bv_allocator_type > matrix_chain_type
Definition bmxor.h:801
bm::xor_sim_model::matr
matrix_chain_type matr
model matrix
Definition bmxor.h:804
bm::xor_sim_model::bv_blocks
bvector_type bv_blocks
blocks digest
Definition bmxor.h:805
bm::xor_sim_params
Parameters for XOR similarity search.
Definition bmxor.h:59