ALP User Documentation 0.7.alpha
Algebraic Programming User Documentation
Loading...
Searching...
No Matches
pregel.hpp
Go to the documentation of this file.
1
2/*
3 * Copyright 2021 Huawei Technologies Co., Ltd.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
142#ifndef _H_GRB_INTERFACES_PREGEL
143#define _H_GRB_INTERFACES_PREGEL
144
145#include <graphblas.hpp>
146#include <graphblas/utils/parser.hpp>
147
148#include <stdexcept> // std::runtime_error
149
150
151namespace grb {
152
153 namespace interfaces {
154
159 namespace config {
160
168
174 NONE = 0,
175
190
210
228
229 };
230
243
244 } // end namespace grb::interfaces::config
245
266 struct PregelState {
267
282 bool &active;
283
292
296 const size_t &num_vertices;
297
301 const size_t &num_edges;
302
306 const size_t &outdegree;
307
311 const size_t &indegree;
312
316 const size_t &round;
317
324 const size_t &vertexID;
325
326 };
327
337 template<
338 typename MatrixEntryType
339 >
340 class Pregel {
341
342 private:
343
345 const size_t n;
346
348 size_t nz;
349
352
354 grb::Vector< bool > activeVertices;
355
357 grb::Vector< bool > haltVotes;
358
360 grb::Vector< bool > buffer;
361
363 grb::Vector< size_t > outdegrees;
364
366 grb::Vector< size_t > indegrees;
367
370
380 void initialize() {
386 > ring;
387 grb::Vector< size_t > ones( n );
388 if( grb::set( ones, 1 ) != SUCCESS ) {
389 throw std::runtime_error( "Could not set vector ones" );
390 }
391 if( grb::set( outdegrees, 0 ) != SUCCESS ) {
392 throw std::runtime_error( "Could not initialise outdegrees" );
393 }
394 if( grb::mxv< grb::descriptors::dense >(
395 outdegrees, graph, ones, ring
396 ) != SUCCESS
397 ) {
398 throw std::runtime_error( "Could not compute outdegrees" );
399 }
400 if( grb::set( indegrees, 0 ) != SUCCESS ) {
401 throw std::runtime_error( "Could not initialise indegrees" );
402 }
403 if( grb::mxv<
405 >(
406 indegrees, graph, ones, ring
407 ) != SUCCESS ) {
408 throw std::runtime_error( "Could not compute indegrees" );
409 }
410 if( grb::set< grb::descriptors::use_index >(
411 IDs, 0
412 ) != SUCCESS
413 ) {
414 throw std::runtime_error( "Could not compute vertex IDs" );
415 }
416 }
417
418
419 protected:
420
427 template< typename IType >
428 Pregel(
429 const size_t _n,
430 IType _start, const IType _end,
431 const grb::IOMode _mode
432 ) :
433 n( _n ),
434 graph( _n, _n ),
435 activeVertices( _n ),
436 haltVotes( _n ),
437 buffer( _n ),
438 outdegrees( _n ),
439 indegrees( _n ),
440 IDs( _n )
441 {
442 if( grb::ncols( graph ) != grb::nrows( graph ) ) {
443 throw std::runtime_error( "Input graph is bipartite" );
444 }
446 graph, _start, _end, _mode
447 ) != SUCCESS ) {
448 throw std::runtime_error( "Could not build graph" );
449 }
450 nz = grb::nnz( graph );
451 initialize();
452 }
453
454
455 public:
456
500 template< typename IType >
502 const size_t _m, const size_t _n,
503 IType _start, const IType _end,
504 const grb::IOMode _mode
505 ) : Pregel( std::max( _m, _n ), _start, _end, _mode ) {}
506
641 template<
642 class Op,
643 template< typename > class Id,
644 class Program,
645 typename IOType,
646 typename GlobalProgramData,
647 typename IncomingMessageType,
648 typename OutgoingMessageType
649 >
651 const Program program,
652 grb::Vector< IOType > &vertex_state,
653 const GlobalProgramData &data,
656 size_t &rounds,
659 const size_t max_rounds = 0
660 ) {
661 static_assert( grb::is_operator< Op >::value &&
663 "The combiner must be an associate operator"
664 );
665 static_assert( std::is_same< typename Op::D1, IncomingMessageType >::value,
666 "The combiner left-hand input domain should match the incoming message "
667 "type." );
668 static_assert( std::is_same< typename Op::D1, IncomingMessageType >::value,
669 "The combiner right-hand input domain should match the incoming message "
670 "type." );
671 static_assert( std::is_same< typename Op::D1, IncomingMessageType >::value,
672 "The combiner output domain should match the incoming message type." );
673
674 // set default output
675 rounds = 0;
676
677 // sanity checks
678 if( grb::size(vertex_state) != n ) {
679 return MISMATCH;
680 }
681 if( grb::size(in) != n ) {
682 return MISMATCH;
683 }
684 if( grb::size(out) != n ) {
685 return MISMATCH;
686 }
687 if( grb::capacity(vertex_state) != n ) {
688 return ILLEGAL;
689 }
690 if( grb::capacity(in) != n ) {
691 return ILLEGAL;
692 }
693 if( grb::capacity(out) != n ) {
694 return ILLEGAL;
695 }
696 if( config::out_sparsify && grb::capacity(out_buffer) != n ) {
697 return ILLEGAL;
698 }
699 if( grb::nnz(vertex_state) != n ) {
700 return ILLEGAL;
701 }
702
703 // define some monoids and semirings
707 > orMonoid;
708
712 > andMonoid;
713
715 Op,
717 IncomingMessageType, bool, IncomingMessageType
718 >,
719 Id,
721 > ring;
722
723 // set initial round ID
724 size_t step = 0;
725
726 // activate all vertices
727 grb::RC ret = grb::set( activeVertices, true );
728
729 // initialise halt votes to all-false
730 if( ret == SUCCESS ) {
731 ret = grb::set( haltVotes, false );
732 }
733
734 // set default incoming message
735 if( ret == SUCCESS && grb::nnz(in) < n ) {
736#ifdef _DEBUG
737 if( grb::nnz(in) > 0 ) {
738 std::cerr << "Overwriting initial incoming messages since it was not a "
739 << "dense vector\n";
740 }
741#endif
742 ret = grb::set( in, Id< IncomingMessageType >::value() );
743 }
744
745 // reset outgoing buffer
746 size_t out_nnz = n;
747 if( ret == SUCCESS ) {
748 ret = grb::set( out, Id< OutgoingMessageType >::value() );
749 }
750
751 // return if initialisation failed
752 if( ret != SUCCESS ) {
753 assert( ret == FAILED );
754 std::cerr << "Error: initialisation failed, but if workspace holds full "
755 << "capacity, initialisation should never fail. Please submit a bug "
756 << "report.\n";
757 return PANIC;
758 }
759
760 // while there are active vertices, execute
761 while( ret == SUCCESS ) {
762
763 assert( max_rounds == 0 || step < max_rounds );
764 // run one step of the program
765 ret = grb::eWiseLambda(
766 [
767 this,
768 &vertex_state,
769 &in,
770 &out,
771 &program,
772 &step,
773 &data
774 ]( const size_t i ) {
775 // create Pregel struct
776 PregelState pregel = {
777 activeVertices[ i ],
778 haltVotes[ i ],
779 n,
780 nz,
781 outdegrees[ i ],
782 indegrees[ i ],
783 step,
784 IDs[ i ]
785 };
786 // only execute program on active vertices
787 assert( activeVertices[ i ] );
788#ifdef _DEBUG
789 std::cout << "Vertex " << i << " remains active in step " << step
790 << "\n";
791#endif
792 program(
793 vertex_state[ i ],
794 in[ i ],
795 out[ i ],
796 data,
797 pregel
798 );
799#ifdef _DEBUG
800 std::cout << "Vertex " << i << " sends out message " << out[ i ]
801 << "\n";
802#endif
803 }, activeVertices, vertex_state, in, out, outdegrees, haltVotes
804 );
805
806 // increment counter
807 (void) ++step;
808
809 // check if everyone voted to halt
810 if( ret == SUCCESS ) {
811 bool halt = true;
812 ret = grb::foldl< grb::descriptors::structural >(
813 halt, haltVotes, activeVertices, andMonoid
814 );
815 assert( ret == SUCCESS );
816 if( ret == SUCCESS && halt ) {
817#ifdef _DEBUG
818 std::cout << "\t All active vertices voted to halt; "
819 << "terminating Pregel program.\n";
820#endif
821 break;
822 }
823 }
824
825 // update active vertices
826 if( ret == SUCCESS ) {
827#ifdef _DEBUG
828 std::cout << "\t Number of active vertices was "
829 << grb::nnz( activeVertices ) << ", and ";
830#endif
831 ret = grb::clear( buffer );
832 ret = ret ? ret : grb::set( buffer, activeVertices, true );
833 std::swap( buffer, activeVertices );
834#ifdef _DEBUG
835 std::cout << " has now become " << grb::nnz( activeVertices ) << "\n";
836#endif
837 }
838
839 // check if there is a next round
840 const size_t curActive = grb::nnz( activeVertices );
841 if( ret == SUCCESS && curActive == 0 ) {
842#ifdef _DEBUG
843 std::cout << "\t All vertices are inactive; "
844 << "terminating Pregel program.\n";
845#endif
846 break;
847 }
848
849 // check if we exceed the maximum number of rounds
850 if( max_rounds > 0 && step > max_rounds ) {
851#ifdef _DEBUG
852 std::cout << "\t Maximum number of Pregel rounds met "
853 << "without the program returning a valid termination condition. "
854 << "Exiting prematurely with a FAILED error code.\n";
855#endif
856 ret = FAILED;
857 break;
858 }
859
860#ifdef _DEBUG
861 std::cout << "\t Starting message exchange\n";
862#endif
863
864 // reset halt votes
865 if( ret == SUCCESS ) {
866 ret = grb::clear( haltVotes );
867 ret = ret ? ret : grb::set< grb::descriptors::structural >(
868 haltVotes, activeVertices, false
869 );
870 }
871
872 // reset incoming buffer
873 if( ret == SUCCESS ) {
874 ret = grb::clear( in );
875 ret = ret ? ret : grb::set< grb::descriptors::structural >(
876 in, activeVertices, Id< IncomingMessageType >::value()
877 );
878 }
879
880 // execute communication
881 if( ret == SUCCESS ) {
882 ret = grb::vxm< grb::descriptors::structural >(
883 in, activeVertices, out, graph, ring
884 );
885 }
886
887 // sparsify and reset outgoing buffer
888 if( config::out_sparsify && ret == SUCCESS ) {
890 (config::out_sparsify == config::WHEN_REDUCED && out_nnz > curActive) ||
891 (config::out_sparsify == config::WHEN_HALVED && curActive <= out_nnz/2)
892 ) {
893 ret = grb::clear( out_buffer );
894 ret = ret ? ret : grb::set< grb::descriptors::structural >(
895 out_buffer, activeVertices, Id< OutgoingMessageType >::value()
896 );
897 std::swap( out, out_buffer );
898 out_nnz = curActive;
899 }
900 }
901
902#ifdef _DEBUG
903 std::cout << "\t Resetting outgoing message fields and "
904 << "starting next compute round\n";
905#endif
906
907 }
908
909#ifdef _DEBUG
910 if( grb::spmd<>::pid() == 0 ) {
911 std::cout << "Info: Pregel exits after " << step
912 << " rounds with error code " << ret
913 << " ( " << grb::toString(ret) << " )\n";
914 }
915#endif
916
917 // done
918 rounds = step;
919 return ret;
920 }
921
928 size_t num_vertices() const noexcept { return n; }
929
936 size_t num_edges() const noexcept { return nz; }
937
950 return graph;
951 }
952
953 };
954
955 } // end namespace ``grb::interfaces''
956
957} // end namespace ``grb''
958
959#endif // end ``_H_GRB_INTERFACES_PREGEL''
960
A generalised monoid.
Definition: monoid.hpp:54
A generalised semiring.
Definition: semiring.hpp:186
Standard identitity for the logical or operator.
Definition: identities.hpp:151
Standard identity for the logical AND operator.
Definition: identities.hpp:178
Standard identity for numerical addition.
Definition: identities.hpp:57
A Pregel run-time instance.
Definition: pregel.hpp:340
const grb::Matrix< MatrixEntryType > & get_matrix() const noexcept
Returns the ALP/GraphBLAS matrix representation of the underlying graph.
Definition: pregel.hpp:949
size_t num_edges() const noexcept
Queries the number of edges of the graph this Pregel instance has been constructed over.
Definition: pregel.hpp:936
size_t num_vertices() const noexcept
Queries the maximum vertex ID for programs running on this Pregel instance.
Definition: pregel.hpp:928
Pregel(const size_t _m, const size_t _n, IType _start, const IType _end, const grb::IOMode _mode)
Constructs a Pregel instance from input iterators over some graph.
Definition: pregel.hpp:501
grb::RC execute(const Program program, grb::Vector< IOType > &vertex_state, const GlobalProgramData &data, grb::Vector< IncomingMessageType > &in, grb::Vector< OutgoingMessageType > &out, size_t &rounds, grb::Vector< OutgoingMessageType > &out_buffer=grb::Vector< OutgoingMessageType >(0), const size_t max_rounds=0)
Executes a given vertex-centric program on this graph.
Definition: pregel.hpp:650
This operator takes the sum of the two input parameters and writes it to the output variable.
Definition: ops.hpp:174
This operator assigns the left-hand input if the right-hand input evaluates true.
Definition: ops.hpp:88
The logical and.
Definition: ops.hpp:491
The logical or.
Definition: ops.hpp:462
This operator assigns the right-hand input if the left-hand input evaluates true.
Definition: ops.hpp:141
For backends that support multiple user processes this class defines some basic primitives to support...
Definition: spmd.hpp:51
The main header to include in order to use the ALP/GraphBLAS API.
RC eWiseLambda(const Func f, const Vector< DataType, backend, Coords > &x, Args...)
Executes an arbitrary element-wise user-defined function f using any number of vectors of equal lengt...
Definition: blas1.hpp:3524
RC mxv(Vector< IOType, backend, Coords > &u, const Vector< InputType3, backend, Coords > &u_mask, const Matrix< InputType2, backend, RIT, CIT, NIT > &A, const Vector< InputType1, backend, Coords > &v, const Vector< InputType4, backend, Coords > &v_mask, const Semiring &semiring=Semiring(), const Phase &phase=EXECUTE, const typename std::enable_if< grb::is_semiring< Semiring >::value &&!grb::is_object< IOType >::value &&!grb::is_object< InputType1 >::value &&!grb::is_object< InputType2 >::value &&!grb::is_object< InputType3 >::value &&!grb::is_object< InputType4 >::value, void >::type *const =nullptr)
Right-handed in-place doubly-masked sparse matrix times vector multiplication, .
Definition: blas2.hpp:243
size_t capacity(const Vector< InputType, backend, Coords > &x) noexcept
Queries the capacity of the given ALP/GraphBLAS container.
Definition: io.hpp:388
RC buildMatrixUnique(Matrix< InputType, implementation > &A, fwd_iterator1 I, const fwd_iterator1 I_end, fwd_iterator2 J, const fwd_iterator2 J_end, fwd_iterator3 V, const fwd_iterator3 V_end, const IOMode mode)
Assigns nonzeroes to the matrix from a coordinate format.
Definition: io.hpp:1335
RC set(Vector< DataType, backend, Coords > &x, const T val, const Phase &phase=EXECUTE, const typename std::enable_if< !grb::is_object< DataType >::value &&!grb::is_object< T >::value, void >::type *const =nullptr) noexcept
Sets all elements of a vector to the given value.
Definition: io.hpp:857
size_t nrows(const Matrix< InputType, backend, RIT, CIT, NIT > &A) noexcept
Requests the row size of a given matrix.
Definition: io.hpp:286
size_t nnz(const Vector< DataType, backend, Coords > &x) noexcept
Request the number of nonzeroes in a given vector.
Definition: io.hpp:479
size_t ncols(const Matrix< InputType, backend, RIT, CIT, NIT > &A) noexcept
Requests the column size of a given matrix.
Definition: io.hpp:339
RC clear(Vector< DataType, backend, Coords > &x) noexcept
Clears a given vector of all nonzeroes.
Definition: io.hpp:574
size_t size(const Vector< DataType, backend, Coords > &x) noexcept
Request the size of a given vector.
Definition: io.hpp:235
SparsificationStrategy
The set of sparsification strategies supported by the ALP/Pregel interface.
Definition: pregel.hpp:167
constexpr const SparsificationStrategy out_sparsify
What sparsification strategy should be applied to the outgoing messages.
Definition: pregel.hpp:242
@ ALWAYS
Always applies the sparsification procedure on both internal and user- defined vertex states.
Definition: pregel.hpp:189
@ WHEN_HALVED
Sparsify only when the resulting vector would have half (or less) its current number of nonzeroes.
Definition: pregel.hpp:227
@ NONE
No sparsification of internal and user-defined vertex states, beyond that which is necessary to bound...
Definition: pregel.hpp:174
@ WHEN_REDUCED
Sparsify only when the resulting vector would indeed be sparser.
Definition: pregel.hpp:209
static constexpr Descriptor transpose_matrix
Transposes the input matrix prior to applying it.
Definition: descriptors.hpp:71
static constexpr Descriptor dense
Indicates that all input and output vectors to an ALP/GraphBLAS primitive are structurally dense.
Definition: descriptors.hpp:151
The ALP/GraphBLAS namespace.
Definition: graphblas.hpp:450
std::string toString(const RC code)
IOMode
The GraphBLAS input and output functionalities can either be used in a sequential or parallel fashion...
Definition: iomode.hpp:67
RC
Return codes of ALP primitives.
Definition: rc.hpp:47
@ ILLEGAL
A call to a primitive has determined that one of its arguments was illegal as per the specification o...
Definition: rc.hpp:143
@ PANIC
Generic fatal error code.
Definition: rc.hpp:68
@ MISMATCH
One or more of the ALP/GraphBLAS objects passed to the primitive that returned this error have mismat...
Definition: rc.hpp:90
@ SUCCESS
Indicates the primitive has executed successfully.
Definition: rc.hpp:54
@ FAILED
Indicates when one of the grb::algorithms has failed to achieve its intended result,...
Definition: rc.hpp:154
The state of the vertex-center Pregel program that the user may interface with.
Definition: pregel.hpp:266
const size_t & num_vertices
The number of vertices in the global graph.
Definition: pregel.hpp:296
bool & voteToHalt
Represents whether this (active) vertex votes to terminate the program.
Definition: pregel.hpp:291
const size_t & num_edges
The number of edges in the global graph.
Definition: pregel.hpp:301
const size_t & indegree
The in-degree of this vertex.
Definition: pregel.hpp:311
bool & active
Represents whether the current vertex is active.
Definition: pregel.hpp:282
const size_t & round
The current round the vertex-centric program is currently executing.
Definition: pregel.hpp:316
const size_t & vertexID
A unique ID of this vertex.
Definition: pregel.hpp:324
const size_t & outdegree
The out-degree of this vertex.
Definition: pregel.hpp:306
Used to inspect whether a given operator or monoid is associative.
Definition: type_traits.hpp:202
Used to inspect whether a given type is an ALP operator.
Definition: type_traits.hpp:104