Assertion error inside HDAGG::partialSparsification for Hdagg_SpTRSV example

[learning-chip]

At the latest commit da104fa, and fixed #4, there is still run-time error for examples/SpTRSV_runtime.cpp. The error occurs during the call to HDAGG::partialSparsification in examples/SpTRSV_runtime.h, in particular this assertion inside partialSparsification:

aggregation/src/hdagg/hdagg.cpp

Lines 2083 to 2086 in da104fa

	//The starting point of the next clique
	col = first + width;
	assert(col <= n);
	clique_ptr_per_thread.push_back(col);

Error messages

With debug build, the error message is:

METIS IS ACTIVATED
Starting SpTrSv Runtime analysis
Write in the existing file SpTrSv_Final_20.csv
Running LL Serial Code - The runtime:1.25e-05
Running LL Levelset Code with #core: 20 - The runtime:1.58e-05
Hdagg_SpTRSV: /work_dir/aggregation/src/hdagg/hdagg.cpp:2085: void HDAGG::partialSparsification(int, int, const int*, const int*, std::vector<int>&, std::vector<int>&, bool): Assertion `col <= n' failed.
Aborted

The "LL Serial" and "LL Levelset" case work fine because they don't call partialSparsification. The "LL Tree + Levelset" and later cases fail at partialSparsification.

With release build it leads to memory errors, likely due to exceeding array bounds:

METIS IS ACTIVATED
Starting SpTrSv Runtime analysis
Write in the existing file SpTrSv_Final_20.csv
Running LL Serial Code - The runtime:1.24e-05
Running LL Levelset Code with #core: 20 - The runtime:1.46e-05
malloc_consolidate(): invalid chunk size
Aborted

The above are using the built-in random matrix generation. Using an external matrix like G2_circuit give a different error, but still memory-related.

Reading matrix /work_dir/matrix_data/G2_circuit/G2_circuit.mtx
METIS IS ACTIVATED
Starting SpTrSv Runtime analysis
Write in the existing file SpTrSv_Final_20.csv
Running LL Serial Code - The runtime:0.0009317
Running LL Levelset Code with #core: 2 - The runtime:0.0016047
Hdagg_SpTRSV: malloc.c:4118: _int_malloc: Assertion `chunk_main_arena (fwd)' failed.
Aborted

Steps to reproduce

git clone https://github.com/sympiler/aggregation
cd aggregation

# debug mode
cmake -DCMAKE_BUILD_TYPE=Debug -S . -B build_debug
cmake --build build_debug
./build_debug/example/Hdagg_SpTRSV  # generates random matrice, same error when reading a mtx file

# release mode
cmake -DCMAKE_BUILD_TYPE=Release -S . -B build_release
cmake --build build_release -j 4
./build_release/example/Hdagg_SpTRSV
# read external matrix file and use less threads than default
./build_release/example/Hdagg_SpTRSV /work_dir/matrix_data/G2_circuit/G2_circuit.mtx 2

The system environment can be reproduced using this trivial Dockerfile that installs GCC 11.3 and CMake 3.22:

FROM ubuntu:22.04

RUN apt-get update \
    && DEBIAN_FRONTEND=noninteractive apt-get install -y \
    git wget vim \
    gcc g++ gfortran \
    libnuma-dev \
    libhwloc-dev \
    libmetis-dev \
    libomp-dev \
    make cmake \
    && rm -rf /var/lib/apt/lists/*

[cheshmi]

Thanks, can you please send a PR?

[learning-chip]

I haven't diagnosed the root cause of error, but simply skipped the cases that calls partialSparsification in order to compile that example program. For example SpTrSv_LL_HDAGG doesn't call sparsification so still runs, but SpTrSv_LL_Tree_HDAGG breaks. However the inspection time of HDAGG is many times slower than Tree_HDAGG, presumably due to lack of sparsification.

[learning-chip]

One clue: The same SpTRSV_runtime.cpp example from the older repo https://github.com/BehroozZare/HDagg-benchmark (as of commit 948b38f) runs fine without array-bound errors. So it must be due to some updates in between.

[cheshmi]

Got it, thanks.
I think HDagg repo is more updated than this for the HDagg algorithm.

[learning-chip]

Hi @cheshmi I found the problem with this repo --

The find_package(OpenMP) in the top-level cmake file is disabled:

aggregation/CMakeLists.txt

Lines 59 to 72 in da104fa

	#find_package(OpenMP)
	if(OpenMP_FOUND)
	if(APPLE) #TODO: there might be a better support
	set(OpenMP_CXX_INCLUDE_DIRS "/usr/local/include/")
	endif()
	include_directories(
	${OpenMP_CXX_INCLUDE_DIRS}
	)
	link_libraries(
	OpenMP::OpenMP_CXX
	)
	add_definitions(-DENABLE_OPENMP)
	add_definitions(-D__OPENMP__)
	endif()

This is probably fine when compiled as a subproject of Sympiler (where OpenMP is found one level higher); but when compiling this aggregation repo as a standalone project, the ENABLE_OPENMP macro and OpenMP flags won't get defined. Then, inside the HDAGG::partialSparsification function:

aggregation/src/hdagg/hdagg.cpp

Lines 2036 to 2042 in da104fa

	#ifdef ENABLE_OPENMP
	int bins = omp_get_num_threads();
	int tid = omp_get_thread_num();
	#else
	int bins =1;
	int tid=1;
	#endif

Both bins and tid will be set to 1, causing a bug when the user wants parallel partitioning.

Uncommenting find_package(OpenMP) fixes the bug. Or maybe using the HAS_PARENT condition to optionally include dependencies.

One the other hand, in the older HDagg-benchmark repo, there is no ENABLE_OPENMP switch, and bins is always set to omp_get_num_threads(), so no such bug.

[learning-chip]

More unit tests for the HDagg procedure (sparsification, grouping, partitioning, ungrouping...) might help prevent future bugs? In the current Catch_tests there seems to be only one test for the simple levelset sptrsv, but not more advanced partitionings like LBC or HDagg. And the test is disabled in cmake file.

[learning-chip]

The current GitHub workflow runs lbc_demo and sptrsv_demo, but not Hdagg_SpTRSV (the executable for SpTRSV_runtime.cpp).

aggregation/.github/workflows/cmakeUbuntu.yml

Lines 37 to 45 in da104fa

	- name: Build
	# Build your program with the given configuration
	run: cmake --build ${{github.workspace}}/build --target lbc lbc_demo sptrsv_demo
	- name: run test 1
	run: |
	${{github.workspace}}/build/example/lbc_demo
	${{github.workspace}}/build/example/sptrsv_demo

If you add lines like

cmake --build ${{github.workspace}}/build --target Hdagg_SpTRSV
${{github.workspace}}/build/example/Hdagg_SpTRSV`, 

you should see the error message in GitHub actions.

[learning-chip]

OK I saw that find_package(OpenMP) was disabled by the commit 5b88309 , presumably to ensure compatibility with the parent Sympiler directory.

May using

if(LBC_IS_TOPLEVEL)
    find_package(OpenMP)
endif()

to avoid duplication. Although I think duplicately calling find_package(OpenMP) is also fine...