Provides implementations for several variants of Radix Hash Join. More...

#include <sched.h>
#include <pthread.h>
#include <stdlib.h>
#include <sys/time.h>
#include <stdio.h>
#include <smmintrin.h>
#include <immintrin.h>
#include "parallel_radix_join.h"
#include "prj_params.h"
#include "task_queue.h"
#include "cpu_mapping.h"
#include "rdtsc.h"
#include "barrier.h"
#include "affinity.h"
#include "generator.h"

Classes
struct	arg_t

struct	part_t

union	cacheline_t

Macros
#define	_GNU_SOURCE

#define	MALLOC_CHECK(M)

#define	HASH_BIT_MODULO(K, MASK, NBITS) (((K) & MASK) >> NBITS)

#define	NEXT_POW_2(V)

#define	MAX(X, Y) (((X) > (Y)) ? (X) : (Y))

#define	SYNC_TIMERS_START(A, TID)

#define	SYNC_TIMER_STOP(T)

#define	SYNC_GLOBAL_STOP(T, TID)

#define	DEBUGMSG(COND, MSG, ...)

#define	TUPLESPERCACHELINE (CACHE_LINE_SIZE/sizeof(tuple_t))

Typedefs
typedef struct arg_t	arg_t

typedef struct part_t	part_t

typedef struct synctimer_t	synctimer_t

typedef int64_t(*	JoinFunction) (const relation_t const, const relation_t const, relation_t const, void output)

Functions
struct arg_t	__attribute__ ((aligned(CACHE_LINE_SIZE)))

int64_t	bucket_chaining_join (const relation_t const R, const relation_t const S, relation_t const tmpR, void output)

uint32_t	get_hist_size (uint32_t relSize) __attribute__((always_inline))

int64_t	histogram_join (const relation_t const R, const relation_t const S, relation_t const tmpR, void output)

void	prefetch (void *addr) __attribute__((always_inline))

int64_t	histogram_optimized_join (const relation_t const R, const relation_t const S, relation_t const tmpR, void output)

void	radix_cluster (relation_t restrict outRel, relation_t restrict inRel, int32_t *restrict hist, int R, int D)

void	radix_cluster_nopadding (relation_t outRel, relation_t inRel, int R, int D)

void	serial_radix_partition (task_t const task, task_queue_t join_queue, const int R, const int D)

void	parallel_radix_partition (part_t *const part)

void	parallel_radix_partition_optimized (part_t *const part)

void *	prj_thread (void *param)

result_t *	join_init_run (relation_t relR, relation_t relS, JoinFunction jf, int nthreads)

result_t *	PRO (relation_t relR, relation_t relS, int nthreads)

result_t *	PRH (relation_t relR, relation_t relS, int nthreads)

result_t *	PRHO (relation_t relR, relation_t relS, int nthreads)

result_t *	RJ (relation_t relR, relation_t relS, int nthreads)

Variables
typedef	__attribute__

int	numalocalize

int32_t **	histR

tuple_t *	relR

tuple_t *	tmpR

int32_t **	histS

tuple_t *	relS

tuple_t *	tmpS

int32_t	numR

int32_t	numS

int64_t	totalR

int64_t	totalS

task_queue_t **	join_queue

task_queue_t **	part_queue

pthread_barrier_t *	barrier

JoinFunction	join_function

int64_t	result

int32_t	my_tid

int	nthreads

threadresult_t *	threadresult

int32_t	parts_processed

uint64_t	timer1

uint64_t	timer2

uint64_t	timer3

struct timeval start	end

tuple_t *	rel

tuple_t *	tmp

int32_t **	hist

int64_t *	output

arg_t *	thrargs

uint64_t	total_tuples

uint32_t	num_tuples

int32_t	R

uint32_t	D

int	relidx

uint32_t	padding

Detailed Description

Provides implementations for several variants of Radix Hash Join.

Author: Cagri Balkesen cagri.nosp@m..bal.nosp@m.kesen.nosp@m.@inf.nosp@m..ethz.nosp@m..ch

Date: Sun Feb 20:19:51 2012

Version

Id: parallel_radix_join.c 4548 2013-12-07 16:05:16Z bcagri

Definition in file parallel_radix_join.c.

Macro Definition Documentation

◆ _GNU_SOURCE

#define _GNU_SOURCE

Definition at line 14 of file parallel_radix_join.c.

◆ DEBUGMSG

#define DEBUGMSG	(	COND,
		MSG,
		...
	)

Debug msg logging method

Definition at line 118 of file parallel_radix_join.c.

◆ HASH_BIT_MODULO

#define HASH_BIT_MODULO	(	K,
		MASK,
		NBITS
	)	(((K) & MASK) >> NBITS)

Definition at line 64 of file parallel_radix_join.c.

◆ MALLOC_CHECK

#define MALLOC_CHECK ( M )

Value:

    if(!M){                                                             \
        printf("[ERROR] MALLOC_CHECK: %s : %d\n", __FILE__, __LINE__);  \
        perror(": malloc() failed!\n");                                 \
        exit(EXIT_FAILURE);                                             \
    }

checks malloc() result

Definition at line 55 of file parallel_radix_join.c.

◆ MAX

#define MAX	(	X,
		Y
	)	(((X) > (Y)) ? (X) : (Y))

Definition at line 84 of file parallel_radix_join.c.

◆ NEXT_POW_2

#define NEXT_POW_2 ( V )

Value:

    do {                                        \
        V--;                                    \
        V |= V >> 1;                            \
        V |= V >> 2;                            \
        V |= V >> 4;                            \
        V |= V >> 8;                            \
        V |= V >> 16;                           \
        V++;                                    \
    } while(0)

compute the next number, greater than or equal to 32-bit unsigned v. taken from "bit twiddling hacks": http://graphics.stanford.edu/~seander/bithacks.html

Definition at line 72 of file parallel_radix_join.c.

◆ SYNC_GLOBAL_STOP

#define SYNC_GLOBAL_STOP	(	T,
		TID
	)

Definition at line 110 of file parallel_radix_join.c.

◆ SYNC_TIMER_STOP

#define SYNC_TIMER_STOP ( T )

Definition at line 109 of file parallel_radix_join.c.

◆ SYNC_TIMERS_START

#define SYNC_TIMERS_START	(	A,
		TID
	)

Definition at line 108 of file parallel_radix_join.c.

Typedef Documentation

◆ arg_t

typedef struct arg_t arg_t

Definition at line 129 of file parallel_radix_join.c.

◆ JoinFunction

typedef int64_t(* JoinFunction) (const relation_t *const, const relation_t *const, relation_t *const, void *output)

Definition at line 132 of file parallel_radix_join.c.

◆ part_t

typedef struct part_t part_t

Definition at line 130 of file parallel_radix_join.c.

◆ synctimer_t

typedef struct synctimer_t synctimer_t

Definition at line 131 of file parallel_radix_join.c.

Variable Documentation

◆ barrier

pthread_barrier_t* barrier

Definition at line 18 of file parallel_radix_join.c.

◆ D

uint32_t D

Definition at line 8 of file parallel_radix_join.c.

◆ end

struct timeval start end

Definition at line 30 of file parallel_radix_join.c.

◆ hist

int32_t** hist

Definition at line 2 of file parallel_radix_join.c.

◆ histR

int32_t** histR

Definition at line 0 of file parallel_radix_join.c.

◆ histS

int32_t** histS

Definition at line 3 of file parallel_radix_join.c.

◆ join_function

JoinFunction join_function

Definition at line 19 of file parallel_radix_join.c.

◆ join_queue

task_queue_t** join_queue

Definition at line 12 of file parallel_radix_join.c.

◆ my_tid

int32_t my_tid

Definition at line 21 of file parallel_radix_join.c.

◆ nthreads

int nthreads

Definition at line 22 of file parallel_radix_join.c.

◆ num_tuples

uint32_t num_tuples

Definition at line 6 of file parallel_radix_join.c.

◆ numalocalize

int numalocalize

extern

An experimental feature to allocate input relations numa-local

Definition at line 47 of file generator.c.

◆ numR

int32_t numR

Definition at line 7 of file parallel_radix_join.c.

◆ numS

int32_t numS

Definition at line 8 of file parallel_radix_join.c.

◆ output

int64_t* output

Definition at line 3 of file parallel_radix_join.c.

◆ padding

uint32_t padding

Definition at line 10 of file parallel_radix_join.c.

◆ part_queue

task_queue_t** part_queue

Definition at line 13 of file parallel_radix_join.c.

◆ parts_processed

int32_t parts_processed

Definition at line 28 of file parallel_radix_join.c.

◆ R

int32_t R

Definition at line 7 of file parallel_radix_join.c.

◆ rel

tuple_t* rel

Definition at line 0 of file parallel_radix_join.c.

◆ relidx

int relidx

Definition at line 9 of file parallel_radix_join.c.

◆ relR

tuple_t* relR

Definition at line 1 of file parallel_radix_join.c.

◆ relS

tuple_t* relS

Definition at line 4 of file parallel_radix_join.c.

◆ result

int64_t result

Definition at line 20 of file parallel_radix_join.c.

◆ thrargs

arg_t* thrargs

Definition at line 4 of file parallel_radix_join.c.

◆ threadresult

threadresult_t* threadresult

Definition at line 25 of file parallel_radix_join.c.

◆ timer1

uint64_t timer1

Definition at line 29 of file parallel_radix_join.c.

◆ timer2

uint64_t timer2

Definition at line 29 of file parallel_radix_join.c.

◆ timer3

uint64_t timer3

Definition at line 29 of file parallel_radix_join.c.

◆ tmp

tuple_t* tmp

Definition at line 1 of file parallel_radix_join.c.

◆ tmpR

tuple_t* tmpR

Definition at line 2 of file parallel_radix_join.c.

◆ tmpS

tuple_t* tmpS

Definition at line 5 of file parallel_radix_join.c.

◆ total_tuples

uint64_t total_tuples

Definition at line 5 of file parallel_radix_join.c.

◆ totalR

int64_t totalR

Definition at line 9 of file parallel_radix_join.c.

◆ totalS

int64_t totalS

Definition at line 10 of file parallel_radix_join.c.

Classes

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ _GNU_SOURCE

◆ DEBUGMSG

◆ HASH_BIT_MODULO

◆ MALLOC_CHECK

◆ MAX

◆ NEXT_POW_2

◆ SYNC_GLOBAL_STOP

◆ SYNC_TIMER_STOP

◆ SYNC_TIMERS_START

Typedef Documentation

◆ arg_t

◆ JoinFunction

◆ part_t

◆ synctimer_t

Variable Documentation

◆ barrier

◆ D

◆ end

◆ hist

◆ histR

◆ histS

◆ join_function

◆ join_queue

◆ my_tid

◆ nthreads

◆ num_tuples

◆ numalocalize

◆ numR

◆ numS

◆ output

◆ padding

◆ part_queue

◆ parts_processed

◆ R

◆ rel

◆ relidx

◆ relR

◆ relS

◆ result

◆ thrargs

◆ threadresult

◆ timer1

◆ timer2

◆ timer3

◆ tmp

◆ tmpR

◆ tmpS

◆ total_tuples

◆ totalR

◆ totalS