Update tree (!4) · Merge requests · Luca Tornatore / dADP

src/adp/adp.c

+27 −23

Changes for src/adp/adp.c: 27 added lines, 23 removed lines.
Original line number	Diff line number	Diff line
		@@ -92,10 +92,10 @@ float_t get_j_ksel_dist(global_context_t* ctx, idx_t j, idx_t ksel, MPI_Win expo
		}
		else
		{
		heap_node el;
		heap_node_t el;
		idx_t pos = j - ctx -> rank_idx_start[owner];
		MPI_Request request;
		int err = MPI_Rget(&el, sizeof(heap_node), MPI_BYTE, owner, (MPI_Aint)((pos * k + ksel) * sizeof(heap_node)), sizeof(heap_node), MPI_BYTE, exposed_ngbh, &request);
		int err = MPI_Rget(&el, sizeof(heap_node_t), MPI_BYTE, owner, (MPI_Aint)((pos * k + ksel) * sizeof(heap_node_t)), sizeof(heap_node_t), MPI_BYTE, exposed_ngbh, &request);
		MPI_Wait(&request,MPI_STATUS_IGNORE);
		return el.value;
		}
		@@ -113,10 +113,10 @@ idx_t get_j_ksel_idx(global_context_t* ctx, idx_t j, idx_t ksel, MPI_Win exposed
		}
		else
		{
		heap_node el;
		heap_node_t el;
		idx_t pos = j - ctx -> rank_idx_start[owner];
		MPI_Request request;
		int err = MPI_Rget(&el, sizeof(heap_node), MPI_BYTE, owner, (MPI_Aint)((pos * k + ksel) * sizeof(heap_node)), sizeof(heap_node), MPI_BYTE, exposed_ngbh, &request);
		int err = MPI_Rget(&el, sizeof(heap_node_t), MPI_BYTE, owner, (MPI_Aint)((pos * k + ksel) * sizeof(heap_node_t)), sizeof(heap_node_t), MPI_BYTE, exposed_ngbh, &request);
		MPI_Wait(&request,MPI_STATUS_IGNORE);
		return el.array_idx;
		}
		@@ -176,7 +176,7 @@ void compute_density_kstarnn_rma_v2(global_context_t* ctx, const float_t d, int

		MPI_Win exposed_ngbh;
		MPI_Win_create( ctx -> __local_heap_buffers,
		ctx -> local_n_points * ctx -> k * sizeof(heap_node),
		ctx -> local_n_points * ctx -> k * sizeof(heap_node_t),
		1, MPI_INFO_NULL,
		ctx -> mpi_communicator,
		&exposed_ngbh);
		@@ -186,7 +186,7 @@ void compute_density_kstarnn_rma_v2(global_context_t* ctx, const float_t d, int
		int i_have_finished = 0;
		int all_have_finished = 0;
		int finished_points = 0;
		heap_node* scratch_heap_nodes = (heap_node)MY_MALLOC(ctx -> local_n_points sizeof(heap_node));
		heap_node_t* scratch_heap_node_ts = (heap_node_t)MY_MALLOC(ctx -> local_n_points sizeof(heap_node_t));

		for(idx_t j = 4; j < kMAX - 1; ++j)
		{
		@@ -217,17 +217,17 @@ void compute_density_kstarnn_rma_v2(global_context_t* ctx, const float_t d, int

		if(owner == ctx -> mpi_rank)
		{
		scratch_heap_nodes[i] = ctx -> local_datapoints[pos].ngbh[ksel];
		scratch_heap_node_ts[i] = ctx -> local_datapoints[pos].ngbh[ksel];
		}
		else
		{
		// if(pos > ctx -> rank_n_points[owner]) printf("NOPE HERE from rank %d %lu %d\n", ctx -> mpi_rank, pos, ctx -> rank_n_points[owner]);
		MPI_Get(scratch_heap_nodes + i,
		sizeof(heap_node),
		MPI_Get(scratch_heap_node_ts + i,
		sizeof(heap_node_t),
		MPI_BYTE,
		owner,
		(MPI_Aint)((pos * (idx_t)(ctx -> k) + ksel) * sizeof(heap_node)),
		sizeof(heap_node),
		(MPI_Aint)((pos * (idx_t)(ctx -> k) + ksel) * sizeof(heap_node_t)),
		sizeof(heap_node_t),
		MPI_BYTE,
		exposed_ngbh);
		}
		@@ -246,7 +246,7 @@ void compute_density_kstarnn_rma_v2(global_context_t* ctx, const float_t d, int
		{
		float_t vvi, vvj, vp, dL;
		vvi = local_datapoints[i].ngbh[ksel].value;
		vvj = scratch_heap_nodes[i].value;
		vvj = scratch_heap_node_ts[i].value;
		vp = (vvi + vvj)*(vvi + vvj);
		dL = -2.0 * ksel * log(4.vvivvj/vp);

		@@ -293,7 +293,7 @@ void compute_density_kstarnn_rma_v2(global_context_t* ctx, const float_t d, int
		MPI_Win_fence(0, exposed_ngbh);
		MPI_Win_free(&exposed_ngbh);

		free(scratch_heap_nodes);
		free(scratch_heap_node_ts);

		#if defined(WRITE_DENSITY)
		/* densities */
		@@ -301,24 +301,28 @@ void compute_density_kstarnn_rma_v2(global_context_t* ctx, const float_t d, int
		float_t* gs = (float_t)MY_MALLOC(ctx -> local_n_points sizeof(float_t));
		idx_t* ks = (idx_t)MY_MALLOC(ctx -> local_n_points sizeof(idx_t));

		for(int i = 0; i < ctx -> local_n_points; ++i) den[i] = ctx -> local_datapoints[i].log_rho;
		for(int i = 0; i < ctx -> local_n_points; ++i) ks[i] = ctx -> local_datapoints[i].kstar;
		for(int i = 0; i < ctx -> local_n_points; ++i) gs[i] = ctx -> local_datapoints[i].g;
		for(int i = 0; i < ctx -> local_n_points; ++i)
		{
		den[i] = ctx -> local_datapoints[i].log_rho;
		ks[i] = ctx -> local_datapoints[i].kstar;
		gs[i] = ctx -> local_datapoints[i].g;
		}

		ordered_buffer_to_file(ctx, den, sizeof(float_t), ctx -> local_n_points, "bb/ordered_density.npy");
		ordered_buffer_to_file(ctx, ks, sizeof(idx_t), ctx -> local_n_points, "bb/ks.npy");
		ordered_buffer_to_file(ctx, gs, sizeof(float_t), ctx -> local_n_points, "bb/g.npy");

		ordered_data_to_file(ctx, "bb/ordered_data.npy");
		free(gs);
		free(den);
		free(ks);

		#endif
		return;


		}

		float_t get_j_ksel_dist_v2(global_context_t* ctx, idx_t i, idx_t j, idx_t ksel, int* flags, heap_node* tmp_heap_nodes, MPI_Win* exposed_ngbh)
		float_t get_j_ksel_dist_v2(global_context_t* ctx, idx_t i, idx_t j, idx_t ksel, int* flags, heap_node_t* tmp_heap_node_ts, MPI_Win* exposed_ngbh)
		{
		if(flags[i])
		{
		@@ -335,14 +339,14 @@ float_t get_j_ksel_dist_v2(global_context_t* ctx, idx_t i, idx_t j, idx_t ksel,
		//RMA
		flags[i] = 0;
		idx_t pos = j - ctx -> rank_idx_start[owner];
		MPI_Get(tmp_heap_nodes + i, sizeof(heap_node), MPI_BYTE, owner, (MPI_Aint)((pos * k + ksel) * sizeof(heap_node)), sizeof(heap_node), MPI_BYTE, *exposed_ngbh);
		MPI_Get(tmp_heap_node_ts + i, sizeof(heap_node_t), MPI_BYTE, owner, (MPI_Aint)((pos * k + ksel) * sizeof(heap_node_t)), sizeof(heap_node_t), MPI_BYTE, *exposed_ngbh);
		return 0;
		}
		}
		else
		{
		flags[i] = 1;
		return tmp_heap_nodes[i].value;
		return tmp_heap_node_ts[i].value;
		}
		}

		@@ -745,7 +749,7 @@ clusters_t Heuristic1(global_context_t *ctx)
		*
		* optimized v2 use a queue of center removal and then exchange them
		**/
		heap_node* to_remove_mask = (heap_node)MY_MALLOC(nsizeof(heap_node));
		heap_node_t* to_remove_mask = (heap_node_t)MY_MALLOC(nsizeof(heap_node_t));

		for(idx_t p = 0; p < n; ++p)
		{
		@@ -1401,7 +1405,7 @@ void Heuristic2(global_context_t* ctx, clusters_t* cluster)

		MPI_Win dp_info_win, ngbh_win;
		MPI_Win_create(ctx -> local_datapoints, ctx -> local_n_points * sizeof(datapoint_info_t), 1, MPI_INFO_NULL, ctx -> mpi_communicator, &dp_info_win);
		MPI_Win_create(ctx -> __local_heap_buffers, ctx -> local_n_points * ctx -> k * sizeof(heap_node), 1, MPI_INFO_NULL, ctx -> mpi_communicator, &ngbh_win);
		MPI_Win_create(ctx -> __local_heap_buffers, ctx -> local_n_points * ctx -> k * sizeof(heap_node_t), 1, MPI_INFO_NULL, ctx -> mpi_communicator, &ngbh_win);

		MPI_Win_fence(0, dp_info_win);
		MPI_Win_fence(0, ngbh_win);
		@@ -2478,7 +2482,7 @@ void Heuristic3(global_context_t* ctx, clusters_t* cluster, float_t Z, int halo)
		for(int i = 0; i < ctx -> local_n_points; ++i) cl[i] = ctx -> local_datapoints[i].cluster_idx;

		ordered_buffer_to_file(ctx, cl, sizeof(int), ctx -> local_n_points, "bb/final_assignment.npy");
		ordered_data_to_file(ctx, "bb/ordered_data.npy");
		//ordered_data_to_file(ctx, "bb/ordered_data.npy");

		free(cl);

src/common/common.c

+9 −5

Changes for src/common/common.c: 9 added lines, 5 removed lines.
Original line number	Diff line number	Diff line
		#include "common.h"
		#include "mpi.h"
		#include <stdlib.h>
		#include <time.h>

		#define ARRAY_INCREMENT 100
		@@ -15,11 +16,13 @@ void get_context(global_context_t* ctx)
		ctx -> local_data = NULL;
		ctx -> lb_box = NULL;
		ctx -> ub_box = NULL;
		ctx -> og_idxs = NULL;
		ctx -> rank_n_points = (idx_t)malloc(ctx -> world_size sizeof(idx_t));
		ctx -> rank_idx_start = (idx_t)malloc(ctx -> world_size sizeof(idx_t));
		ctx -> local_datapoints = NULL;
		ctx -> __local_heap_buffers = NULL;
		ctx -> input_data_in_float32 = -1;
		ctx -> local_tree_type = KD;
		ctx -> dims = 0;
		ctx -> k = 300;
		ctx -> z = 3;
		@@ -160,10 +163,10 @@ void print_error_code(int err)
		void free_context(global_context_t* ctx)
		{

		FREE_NOT_NULL(ctx -> local_data);
		// FREE_NOT_NULL(ctx -> local_data);
		FREE_NOT_NULL(ctx -> ub_box);
		FREE_NOT_NULL(ctx -> lb_box);
		//FREE_NOT_NULL(ctx -> __local_heap_buffers);
		FREE_NOT_NULL(ctx -> og_idxs);
		if(ctx -> __local_heap_buffers) MPI_Free_mem(ctx -> __local_heap_buffers);


		@@ -179,10 +182,10 @@ void free_context(global_context_t* ctx)

		void free_pointset(pointset_t* ps)
		{
		if(ps -> data)
		if(ps -> datapoints)
		{
		free(ps -> data);
		ps -> data = NULL;
		free(ps -> datapoints);
		ps -> datapoints = NULL;
		}

		if(ps -> ub_box)
		@@ -210,6 +213,7 @@ void mpi_printf(global_context_t* ctx, const char *fmt, ...)
		// myflush(stdout);
		va_end(l);
		}
		fflush(stdout);
		}

		void generate_random_matrix(

src/common/common.h

+30 −8

Changes for src/common/common.h: 30 added lines, 8 removed lines.
Original line number	Diff line number	Diff line
		@@ -10,7 +10,8 @@
		#define DEFAULT_MSG_LEN 10000000
		//#include <stdarg.h>

		#define PARALLEL_FIX_BORDERS
		// #define PARALLEL_FIX_BORDERS
		// #define WRITE_SHUFFLED_DATA
		// #define WRITE_NGBH
		// #define WRITE_TOP_NODES
		// #define WRITE_DENSITY
		@@ -25,6 +26,9 @@
		// #define PRINT_H2_COMM_SCHEME
		// #define PRINT_H1_CLUSTER_ASSIGN_COMPLETION
		// #define PRINT_ORDERED_BUFFER
		// #define PRINT_BALANCE_FACTOR
		// #define CHECK_CORRECT_EXCHANGE
		// #define DUMP_NGBH_KNN

		#define DEFAULT_STR_LEN 200

		@@ -50,14 +54,17 @@
		#define MY_TRUE 1
		#define MY_FALSE 0

		#define HERE printf("%d in file %s reached line %d\n", ctx -> mpi_rank, __FILE__, __LINE__); MPI_Barrier(ctx -> mpi_communicator);
		#define HERE printf("%d in file %s reached line %d\n", ctx -> mpi_rank, __FILE__, __LINE__); fflush(stdout); MPI_Barrier(ctx -> mpi_communicator);

		#define CHECK_ALLOCATION(x) if(!x){printf("[!!!] %d rank encountered failed allocation: %s at line %s \n", ctx -> mpi_rank, __FILE__, __LINE__ ); exit(1);};


		#define CHECK_ALLOCATION_NO_CTX(x) if(!x){printf("[!!!] Failed allocation: %s at line %d \n", __FILE__, __LINE__ ); exit(1);}
		#ifndef MY_MALLOC
		#define MY_MALLOC(n) ({void* p = calloc(n,1); CHECK_ALLOCATION_NO_CTX(p); p; })
		#endif

		#define DB_PRINT(...) printf(__VA_ARGS__)
		#define DB_PRINT(...) printf(__VA_ARGS__); fflush(stdout)
		#ifdef NDEBUG
		#undef DB_PRINT(...)
		#define DB_PRINT(...)
		@@ -93,11 +100,14 @@
		MPI_Reduce(&time, &avg, 1, MPI_DOUBLE, MPI_SUM, 0, ctx -> mpi_communicator); \
		MPI_Reduce(&time, &min, 1, MPI_DOUBLE, MPI_MIN, 0, ctx -> mpi_communicator); \
		MPI_Reduce(&time, &max, 1, MPI_DOUBLE, MPI_MAX, 0, ctx -> mpi_communicator); \
		MPI_Barrier(ctx->mpi_communicator); \
		MPI_DB_PRINT("%50.50s -> [avg: %.2lfs, min: %.2lfs, max: %.2lfs]\n", sec_name, avg/((double)ctx -> world_size), min, max); \
		fflush(stdout); \
		} \
		else \
		{ \
		MPI_DB_PRINT("%s\n", sec_name);\
		fflush(stdout); \
		}\
		}

		@@ -128,11 +138,20 @@
		#define LOG_END
		#endif

		#ifndef POINT
		#define POINT
		typedef struct point_t
		{
		idx_t array_idx;
		float_t* data;
		} point_t;
		#endif

		typedef struct datapoint_info_t {
		/*
		* datapoint object
		*/
		heap_node* ngbh; //heap object stores nearest neighbors of each point
		heap_node_t* ngbh; //heap object stores nearest neighbors of each point
		int is_center; //flag signaling if a point is a cluster center
		int cluster_idx; //cluster index
		idx_t array_idx; //global index of the point in the dataset
		@@ -143,6 +162,7 @@ typedef struct datapoint_info_t {
		float_t log_rho_err; //
		} datapoint_info_t;

		enum local_tree_type {VP, KD};

		typedef struct global_context_t
		{
		@@ -154,8 +174,8 @@ typedef struct global_context_t
		int __processor_name_len; //processor name len
		int world_size;
		int mpi_rank; //rank of the processor
		uint32_t dims; //number of dimensions of the dataset
		idx_t k; //number of neighbors
		uint32_t dims; //number of dimensions of the dataset
		float_t z; //z parameter
		float_t* local_data; //pointer to the dataset stored into the node
		float_t* lb_box; //bounding box of the dataset
		@@ -166,10 +186,12 @@ typedef struct global_context_t
		datapoint_info_t* local_datapoints; //pointer to the datapoint properties
		idx_t* rank_idx_start; //starting index of datapoints in each processor
		idx_t* rank_n_points; //processor name
		heap_node* __local_heap_buffers; //buffer that stores nearest neighbors
		idx_t* og_idxs; //original indexes
		heap_node_t* __local_heap_buffers; //buffer that stores nearest neighbors
		MPI_Comm mpi_communicator; //mpi communicator
		char input_data_file[DEFAULT_STR_LEN];
		enum local_tree_type local_tree_type; //local tree strategy
		int input_data_in_float32;
		char input_data_file[DEFAULT_STR_LEN];
		char output_assignment_file[DEFAULT_STR_LEN];
		char output_data_file[DEFAULT_STR_LEN];
		} global_context_t;
		@@ -184,7 +206,7 @@ typedef struct pointset_t
		size_t n_points;
		size_t __capacity;
		uint32_t dims;
		float_t* data;
		point_t* datapoints;
		float_t* lb_box;
		float_t* ub_box;
		} pointset_t;

src/main/main.c

+151 −72

Changes for src/main/main.c: 151 added lines, 72 removed lines.
Original line number	Diff line number	Diff line
		@@ -4,32 +4,10 @@
		#include "../common/common.h"
		#include "../tree/tree.h"
		#include "../adp/adp.h"
		#include <string.h>
		#include <unistd.h>
		#include <getopt.h>


		#ifdef AMONRA
		#pragma message "Hi, you are on amonra"
		#define OUT_CLUSTER_ASSIGN "/beegfs/ftomba/phd/results/final_assignment.npy"
		#define OUT_DATA "/beegfs/ftomba/phd/results/ordered_data.npy"
		#endif

		#ifdef LEONARDO
		#define OUT_CLUSTER_ASSIGN "/leonardo_scratch/large/userexternal/ftomba00/out_dadp/final_assignment.npy"
		#define OUT_DATA "/leonardo_scratch/large/userexternal/ftomba00/out_dadp/ordered_data.npy"
		#endif

		#ifdef LUMI
		#define OUT_CLUSTER_ASSIGN "~/scratch_dadp/out_dadp/final_assignment.npy"
		#define OUT_DATA "~/scratch_dadp/out_dadp/ordered_data.npy"
		#endif

		#ifndef OUT_CLUSTER_ASSIGN
		#define OUT_CLUSTER_ASSIGN "final_assignment.npy"
		#define OUT_DATA "ordered_data.npy"
		#endif


		#ifdef THREAD_FUNNELED
		#define THREAD_LEVEL MPI_THREAD_FUNNELED
		#else
		@@ -42,10 +20,10 @@ struct option long_options[] =
		{"in-data" , required_argument, 0, 'i'},
		{"in-dtype", required_argument, 0, 't'},
		{"in-dims" , required_argument, 0, 'd'},
		{"out-data", optional_argument, 0, 'o'},
		{"out-assignment", optional_argument, 0, 'a'},
		{"out-directory", required_argument, 0, 'o'},
		{"kngbh", optional_argument, 0, 'k'},
		{"z", optional_argument, 0, 'z'},
		{"knn-strategy", optional_argument, 0, 's'},
		{"help", optional_argument, 0, 'h'},
		{0, 0, 0, 0}
		};
		@@ -57,12 +35,10 @@ const char* help = "Distributed Advanced Density Peak\n"\
		" -d --in-dims (required) number of dimensions of the data file, dadp expects something\n"\
		" of the form N x d where N is inferred from the lenght of the\n"\
		" data file\n"\
		" -o --out-data (optional) output path for the data, the datafile is shuffled between\n"\
		" mpi tasks and datapoints are ordered default is `out_data` \n"\
		" -a --out-assignment (optional) output path for the cluster assignment output ranges [0 ... Nc - 1]\n"\
		" for core points halo points have indices [-Nc ... -1] conversion\n"\
		" of idx for an halo point is cluster_idx = -halo_idx - 1, default is `out_assignment`\n"\
		" -o --out-directory (required) output path for the data, cluster assignment and original indices \n"\
		" of the datapoints. Produces files like `data.[rank]`, `og_idx.[rank]` and `assignment.[rank]`\n"\
		" -k --kngbh (optional) number of nearest neighbors to compute\n"\
		" -s --knn-strategy (optional) strategy for local knn (allowed values 'kd' for kdtree, 'vp' for ball-tree (vantage point)\n"\
		" -z --z (optional) number of nearest neighbors to compute\n";

		void parse_args(global_context_t* ctx, int argc, char** argv)
		@@ -71,10 +47,8 @@ void parse_args(global_context_t* ctx, int argc, char** argv)
		int opt;
		int input_file_set = 0;
		int input_type_set = 0;
		snprintf(ctx -> output_assignment_file, DEFAULT_STR_LEN, "%s", OUT_CLUSTER_ASSIGN);
		snprintf(ctx -> output_data_file, DEFAULT_STR_LEN, "%s", OUT_DATA);

		while((opt = getopt_long(argc, argv, "i:t:d:o:a:k:z:h", long_options, NULL)) != -1)
		while((opt = getopt_long(argc, argv, "i:t:d:o:k:z:hs:", long_options, NULL)) != -1)
		{
		switch(opt)
		{
		@@ -104,9 +78,6 @@ void parse_args(global_context_t* ctx, int argc, char** argv)
		case 'o':
		strncpy(ctx -> output_data_file, optarg, DEFAULT_STR_LEN);
		break;
		case 'a':
		strncpy(ctx -> output_assignment_file, optarg, DEFAULT_STR_LEN);
		break;
		case 'k':
		ctx -> k = atoi(optarg);
		break;
		@@ -118,6 +89,22 @@ void parse_args(global_context_t* ctx, int argc, char** argv)
		MPI_Finalize();
		exit(0);

		case 's':
		if(strncmp("vp", optarg, 2) == 0)
		{
		ctx -> local_tree_type = VP;
		}
		else if(strncmp("kd", optarg, 2) == 0)
		{
		ctx -> local_tree_type = KD;
		}
		else
		{
		printf("Cannot find valid local tree type selection, exiting\n");
		exit(0);
		}
		break;

		default:
		mpi_printf(ctx, "%s\n", help);
		MPI_Finalize();
		@@ -160,8 +147,7 @@ void print_hello(global_context_t* ctx)
		mpi_printf(ctx, "Data file .............> %s\n", ctx -> input_data_file);
		mpi_printf(ctx, "Input Type .............> float%d\n", ctx -> input_data_in_float32 ? 32 : 64);
		mpi_printf(ctx, "Dimensions .............> %d\n", ctx -> dims);
		mpi_printf(ctx, "Output data file .......> %s\n", ctx -> output_data_file);
		mpi_printf(ctx, "Output assignment file -> %s\n", ctx -> output_assignment_file);
		mpi_printf(ctx, "Output directory .......> %s\n", ctx -> output_data_file);
		mpi_printf(ctx, "k ......................> %lu\n", ctx -> k);
		mpi_printf(ctx, "Z ......................> %.2lf\n", ctx -> z);
		mpi_printf(ctx, "\nRUNNING!\n");
		@@ -251,18 +237,36 @@ void simulate_master_read_and_scatter(int dims, size_t n, global_context_t *ctx)
		TIME_DEF
		double elapsed_time;

		int halo = MY_FALSE;
		int halo = MY_TRUE;
		float_t tol = 0.002;

		if(I_AM_MASTER && ctx -> world_size <= 6)
		if(ctx -> world_size <= 6)
		{
		test_file_path(ctx -> output_data_file);
		test_file_path(ctx -> output_assignment_file);
		if(I_AM_MASTER)
		{
		char out_file[200];

		snprintf(out_file, 200, "%s/og_idx", ctx->output_data_file);
		test_file_path(out_file);

		snprintf(out_file, 200, "%s/assignment", ctx->output_data_file);
		test_file_path(out_file);

		snprintf(out_file, 200, "%s/data", ctx->output_data_file);
		test_file_path(out_file);
		}
		}
		else
		{
		test_distributed_file_path(ctx, ctx -> output_data_file);
		test_distributed_file_path(ctx, ctx -> output_assignment_file);
		char out_file[200];
		snprintf(out_file, 200, "%s/og_idx", ctx->output_data_file);
		test_distributed_file_path(ctx, out_file);

		snprintf(out_file, 200, "%s/assignment", ctx->output_data_file);
		test_distributed_file_path(ctx, out_file);

		snprintf(out_file, 200, "%s/data", ctx->output_data_file);
		test_distributed_file_path(ctx, out_file);
		}


		@@ -345,14 +349,6 @@ void simulate_master_read_and_scatter(int dims, size_t n, global_context_t *ctx)

		uint64_t global_bin_counts_int = (uint64_t )MY_MALLOC(k_global * sizeof(uint64_t));

		pointset_t original_ps;
		original_ps.data = ctx->local_data;
		original_ps.dims = ctx->dims;
		original_ps.n_points = ctx->local_n_points;
		original_ps.lb_box = (float_t)MY_MALLOC(ctx -> dims sizeof(float_t));
		original_ps.ub_box = (float_t)MY_MALLOC(ctx -> dims sizeof(float_t));


		top_kdtree_t tree;
		TIME_START;
		top_tree_init(ctx, &tree);
		@@ -360,15 +356,11 @@ void simulate_master_read_and_scatter(int dims, size_t n, global_context_t *ctx)
		LOG_WRITE("Initializing global kdtree", elapsed_time);

		TIME_START;
		build_top_kdtree(ctx, &original_ps, &tree, k_global, tol);
		parallel_build_top_kdtree(ctx, &tree, 512);
		exchange_points(ctx, &tree);
		elapsed_time = TIME_STOP;
		LOG_WRITE("Top kdtree build and domain decomposition", elapsed_time);

		TIME_START;
		kdtree_v2 local_tree;
		kdtree_v2_init( &local_tree, ctx -> local_data, ctx -> local_n_points, (unsigned int)ctx -> dims);

		datapoint_info_t* dp_info = (datapoint_info_t)MY_MALLOC(ctx -> local_n_points sizeof(datapoint_info_t));
		for(uint64_t i = 0; i < ctx -> local_n_points; ++i)
		{
		@@ -385,19 +377,63 @@ void simulate_master_read_and_scatter(int dims, size_t n, global_context_t *ctx)
		}
		ctx -> local_datapoints = dp_info;

		build_local_tree(ctx, &local_tree);
		TIME_START;

		void* opaque_local_tree;

		switch(ctx -> local_tree_type)
		{
		case KD:
		{
		kdtree_t local_tree;
		kdtree_initialize( &local_tree, ctx -> local_data, ctx -> local_n_points, (unsigned int)ctx -> dims);


		build_tree_kdtree_parallel(&local_tree);
		// build_tree_kdtree_sample(&local_tree);
		ctx -> local_data = local_tree.data;

		elapsed_time = TIME_STOP;
		LOG_WRITE("Local trees init and build", elapsed_time);
		LOG_WRITE("Local kdtrees init and build", elapsed_time);

		TIME_START;
		MPI_DB_PRINT("----- Performing ngbh search -----\n");
		MPI_Barrier(ctx -> mpi_communicator);

		mpi_ngbh_search(ctx, dp_info, &tree, &local_tree, ctx -> local_data, ctx -> k);
		mpi_all_knn_search_kdtree(ctx, dp_info, &tree, &local_tree, ctx -> k);

		MPI_Barrier(ctx -> mpi_communicator);
		elapsed_time = TIME_STOP;
		LOG_WRITE("Total time for all knn search", elapsed_time)
		LOG_WRITE("Total time for all knn search w. local kdtrees", elapsed_time);
		opaque_local_tree = &local_tree;
		}
		break;
		case VP:
		{
		vptree_t local_tree;
		vptree_initialize( &local_tree, ctx -> local_data, ctx -> local_n_points, (unsigned int)ctx -> dims);


		build_tree_vptree(&local_tree);
		// build_tree_kdtree_sample(&local_tree);
		ctx -> local_data = local_tree.data;

		elapsed_time = TIME_STOP;
		LOG_WRITE("Vptrees init and build", elapsed_time);

		TIME_START;
		MPI_DB_PRINT("----- Performing ngbh search -----\n");
		MPI_Barrier(ctx -> mpi_communicator);

		mpi_all_knn_search_vptree(ctx, dp_info, &tree, &local_tree, ctx -> k);

		MPI_Barrier(ctx -> mpi_communicator);
		elapsed_time = TIME_STOP;
		LOG_WRITE("Total time for all knn search w. vptrees", elapsed_time);
		opaque_local_tree = &local_tree;
		}
		break;
		}



		@@ -439,39 +475,82 @@ void simulate_master_read_and_scatter(int dims, size_t n, global_context_t *ctx)


		TIME_START;
		int* cl = (int)MY_MALLOC(ctx -> local_n_points sizeof(int));
		for(int i = 0; i < ctx -> local_n_points; ++i) cl[i] = ctx -> local_datapoints[i].cluster_idx;
		int* cl = (int)MY_MALLOC(2 ctx -> local_n_points * sizeof(int));
		float_t* data_to_write = (float_t)MY_MALLOC(ctx -> local_n_points ctx -> k * sizeof(float_t));

		switch(ctx -> local_tree_type)
		{
		case KD:
		{
		kdtree_t local_tree = ((kdtree_t)opaque_local_tree);
		for(int i = 0; i < ctx -> local_n_points; ++i)
		{
		cl[i] = ctx -> local_datapoints[i].cluster_idx;
		idx_t idx = local_tree.__points[i].array_idx;
		memcpy(data_to_write + idxctx -> dims, local_tree.__points[i].data, ctx -> dimssizeof(float_t));
		}
		kdtree_free(&local_tree);
		}
		break;

		case VP:
		{
		vptree_t local_tree = ((vptree_t)opaque_local_tree);
		for(int i = 0; i < ctx -> local_n_points; ++i)
		{
		cl[i] = ctx -> local_datapoints[i].cluster_idx;
		idx_t idx = local_tree.__points[i].array_idx;
		memcpy(data_to_write + idxctx -> dims, local_tree.__points[i].data, ctx -> dimssizeof(float_t));
		}
		vptree_free(&local_tree);
		}
		break;

		default:
		break;
		}

		if(ctx -> world_size <= 32)
		{
		big_ordered_buffer_to_file(ctx, cl, sizeof(int), ctx -> local_n_points, ctx -> output_assignment_file);
		big_ordered_buffer_to_file(ctx, ctx -> local_data, sizeof(double), ctx -> local_n_points * ctx -> dims, ctx -> output_data_file);
		char out_file[200];

		free(cl);
		snprintf(out_file, 200, "%s/og_idx", ctx->output_data_file);
		big_ordered_buffer_to_file(ctx, ctx->og_idxs, sizeof(idx_t), ctx -> local_n_points, out_file);

		snprintf(out_file, 200, "%s/assignment", ctx->output_data_file);
		big_ordered_buffer_to_file(ctx, cl, sizeof(int), ctx -> local_n_points, out_file);

		snprintf(out_file, 200, "%s/data", ctx->output_data_file);
		big_ordered_buffer_to_file(ctx, data_to_write, sizeof(double), ctx -> local_n_points * ctx -> dims, out_file);
		}
		else
		{
		distributed_buffer_to_file(ctx, cl, sizeof(int), ctx -> local_n_points, ctx -> output_assignment_file);
		distributed_buffer_to_file(ctx, ctx -> local_data, sizeof(double), ctx -> local_n_points * ctx -> dims, ctx -> output_data_file);
		char out_file[200];

		free(cl);
		snprintf(out_file, 200, "%s/og_idx", ctx->output_data_file);
		distributed_buffer_to_file(ctx, ctx->og_idxs, sizeof(idx_t), ctx -> local_n_points, out_file);

		snprintf(out_file, 200, "%s/assignment", ctx->output_data_file);
		distributed_buffer_to_file(ctx, cl, sizeof(int), ctx -> local_n_points, out_file);

		snprintf(out_file, 200, "%s/data", ctx->output_data_file);
		distributed_buffer_to_file(ctx, data_to_write, sizeof(double), ctx -> local_n_points * ctx -> dims, out_file);
		}



		elapsed_time = TIME_STOP;
		LOG_WRITE("Write results to file", elapsed_time);


		free(cl);
		free(data_to_write);
		top_tree_free(ctx, &tree);
		kdtree_v2_free(&local_tree);
		//clusters_free(&clusters);

		free(send_counts);
		free(displacements);
		//free(dp_info);

		original_ps.data = NULL;
		free_pointset(&original_ps);
		free(global_bin_counts_int);
		}

src/tree/heap.c

deleted100644 → 0

+0 −217

Changes for src/tree/heap.c: 0 added lines, 217 removed lines.
Original line number	Diff line number	Diff line
		#include "heap.h"

		void swap_heap_node(heap_node* a, heap_node* b){
		heap_node tmp;
		memcpy(&tmp,a,sizeof(heap_node));
		memcpy(a,b,sizeof(heap_node));
		memcpy(b,&tmp,sizeof(heap_node));
		return;
		}

		void allocate_heap(heap* H, idx_t n){
		H -> data = (heap_node)malloc(nsizeof(heap_node));
		H -> N = n;
		H -> count = 0;
		return;
		}

		void init_heap(heap* H){
		for(idx_t i = 0; i < H -> N; ++i)
		{
		H -> data[i].value = 0.;
		H -> data[i].array_idx = MY_SIZE_MAX;
		}
		return;
		}

		void free_heap(heap * H){ free(H -> data);}


		void heapify_max_heap(heap* H, idx_t node){
		idx_t nn = node;
		idx_t largest = nn;
		/*
		Found gratest between children of node and boundcheck if the node is a leaf
		*/

		while(1)
		{
		largest = (HEAP_LCH(nn) < H -> N) &&
		(H -> data[HEAP_LCH(nn)].value > H -> data[largest].value ) ? HEAP_LCH(nn) : largest;

		largest = (HEAP_RCH(nn) < H -> N) &&
		(H -> data[HEAP_RCH(nn)].value > H -> data[largest].value ) ? HEAP_RCH(nn) : largest;
		if(largest != nn)
		{
		swap_heap_node(H -> data + nn, H -> data + largest);
		nn = largest;
		}
		else
		{
		break;
		}
		}


		/*
		if(HEAP_LCH(node) < H -> N){
		//if(H -> data[HEAP_LCH(node)].value > H -> data[largest].value ) largest = HEAP_LCH(node);
		largest = (H -> data[HEAP_LCH(nn)].value > H -> data[largest].value ) ? HEAP_LCH(nn) : largest;
		}
		if(HEAP_RCH(node) < H -> N){
		//if(H -> data[HEAP_RCH(node)].value > H -> data[largest].value ) largest = HEAP_RCH(node);
		largest = (H -> data[HEAP_RCH(nn)].value > H -> data[largest].value ) ? HEAP_RCH(nn) : largest;
		}
		if(largest == node){
		return;
		}
		else{
		swap_heap_node(H -> data + node, H -> data + largest);
		heapify_max_heap(H, largest);
		}
		*/
		}


		void set_root_max_heap(heap * H, FLOAT_TYPE val, idx_t array_idx){
		H -> data[0].value = val;
		H -> data[0].array_idx = array_idx;
		heapify_max_heap(H,0);
		return;
		}

		void insert_max_heap_insertion_sort(heap * H,const FLOAT_TYPE val,const idx_t array_idx){
		heap_node tmpNode = {.value = val, .array_idx = array_idx};
		if(H -> count < H -> N)
		{
		idx_t idx = H -> count;
		H -> data[idx] = tmpNode;
		++(H -> count);
		while(idx >= 1)
		{
		if(H -> data[idx].value < H -> data[idx - 1].value)
		{
		swap_heap_node((H -> data) + idx, (H -> data) + idx - 1);
		idx--;
		}
		else
		{
		break;
		}
		}

		}
		else
		{
		if(H -> data[H -> count - 1].value > val)
		{
		idx_t idx = H -> count - 1;
		H -> data[idx] = tmpNode;
		while(idx >= 1)
		{
		if(H -> data[idx].value < H -> data[idx - 1].value)
		{
		swap_heap_node(H -> data + idx, H -> data + idx - 1);
		idx--;
		}
		else
		{
		break;
		}
		}
		}
		}
		return;
		}

		void insert_max_heap(heap * H,const FLOAT_TYPE val,const idx_t array_idx){
		int c1 = H -> count < H -> N;
		int c2 = (val < H -> data[0].value) && (!c1);
		int ctot = c1 + 2*c2;
		switch (ctot) {
		case 1:
		{
		idx_t node = H->count;
		++(H -> count);
		H -> data[node].value = val;
		H -> data[node].array_idx = array_idx;
		/*
		* Push up the node through the heap
		*/
		while(node && H -> data[node].value > H -> data[HEAP_PARENT(node)].value)
		{
		swap_heap_node(H -> data + node, H -> data + HEAP_PARENT(node));
		node = HEAP_PARENT(node);
		//if(node == 0) break;
		}
		}
		break;

		case 2:
		{
		set_root_max_heap(H,val,array_idx);
		}
		break;
		default:
		break;
		}
		/* alternative solution, left here if something breaks*/

		//if(H -> count < H -> N){
		// idx_t node = H->count;
		// ++(H -> count);
		// H -> data[node].value = val;
		// H -> data[node].array_idx = array_idx;
		// /*
		// * Push up the node through the heap
		// */
		// while(node && H -> data[node].value > H -> data[HEAP_PARENT(node)].value)
		// {
		// swap_heap_node(H -> data + node, H -> data + HEAP_PARENT(node));
		// node = HEAP_PARENT(node);
		// //if(node == 0) break;
		// }
		// return;
		//}
		//else if (val < H -> data[0].value)
		//{
		// set_root_max_heap(H,val,array_idx);
		// return;
		//}
		//else
		//{
		// return;
		//}


		}

		#ifdef USE_FLOAT32
		#define EPS 5.96e-08
		#else
		#define EPS 2.11e-16
		#endif

		int cmp_heap_nodes(const void* a, const void* b)
		{
		const heap_node* aa = (const heap_node*)a;
		const heap_node* bb = (const heap_node*)b;
		int val = (aa -> value > bb -> value) - (aa -> value < bb -> value);
		//return vv;
		return val;


		}


		void heap_sort(heap* H){
		idx_t n = H -> N;
		qsort(H -> data, n, sizeof(heap_node),cmp_heap_nodes);
		//for(idx_t i= (H -> N) - 1; i > 0; --i)
		//{
		// swap_heap_node(H -> data, H -> data + i);
		// H -> N = i;
		// heapify_max_heap(H,0);
		//}
		//H -> N = n;
		}

Update tree

Merge request reports