summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--CMakeLists.txt11
-rwxr-xr-xanalysis0510.py10
-rw-r--r--expt_0501.cu1
-rw-r--r--expt_0503.cu4
-rw-r--r--expt_0516.cu2
-rw-r--r--expt_0516_2.cu1
-rw-r--r--expt_0520.cu4
-rw-r--r--expt_0604.cu73
-rw-r--r--read_helper.h5
-rw-r--r--read_helper_p.h111
-rw-r--r--work_0719.cu (renamed from work.cu)0
11 files changed, 205 insertions, 17 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 6fb4891..02efadf 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -87,12 +87,8 @@ set_target_properties(normal_distribution_expt3 PROPERTIES LINKER_LANGUAGE CXX)
add_executable(normal_distribution_expt0702 expt_0702.cpp)
set_target_properties(normal_distribution_expt0702 PROPERTIES LINKER_LANGUAGE CXX)
-add_executable(work work.cu)
-target_link_libraries(work m stdc++)
-
-set_target_properties(work PROPERTIES
- CUDA_SEPARABLE_COMPILATION ON)
-set_target_properties(work PROPERTIES CUDA_ARCHITECTURES "75")
+add_executable(work_0719 work_0719.cu)
+set_cuda_target_base(work_0719)
add_executable(expt_0722 expt_0722.cpp)
set_target_properties(expt_0722 PROPERTIES LINKER_LANGUAGE CXX)
@@ -177,5 +173,6 @@ set_cuda_target_base(expt_0528)
add_executable(expt_0529 expt_0529.cu read_helper.h)
set_cuda_target_base(expt_0529)
-
+add_executable(expt_0604 expt_0604.cu read_helper.h)
+set_cuda_target_base(expt_0604)
diff --git a/analysis0510.py b/analysis0510.py
index 59cc65c..78290ab 100755
--- a/analysis0510.py
+++ b/analysis0510.py
@@ -6,7 +6,7 @@ def read_from_line(line: str) -> dict[str, int | float]:
ret = {}
if 'skip:' in line:
ret.update({'skip': int(line.split('skip:', 1)[1].split(',')[0])})
- ret.update({'sample': int(line.split('length:', 1)[1].split('|', 1)[0])})
+ ret.update({'sample': int(line.split('length:', 1)[1].split('custom time:', 1)[0])})
ret.update({'custom': float(line.split('custom time: ', 1)[1].split('time')[0])})
ret.update({'normal': float(line.rsplit('time:', 1)[1])})
return ret
@@ -30,6 +30,11 @@ def get_array_summary(sz: list[float]) -> tuple[str, str]:
return f'{middle:.6f}', f'{avg:.6f}'
+def calc_improve(element: list[int]) -> float:
+ a, b = list(map(float, element[:2]))
+ return a / b if a > b else b / a
+
+
def read(file: str, need_calc: bool = False, output_latex: bool = False) -> None:
items = {}
with open(file) as fin:
@@ -50,8 +55,9 @@ def read(file: str, need_calc: bool = False, output_latex: bool = False) -> None
new_result[key][x].append(element[x])
print(*keys)
for key, value in new_result.items():
- column = list(get_array_summary(value[x]) for x in keys)
+ column = list(get_array_summary(value[x])[1] for x in keys)
if output_latex:
+ column.append(f'{calc_improve(column):.6f}')
column = list(map(str, column))
column.insert(0, str(key))
print('\\hline\n', ' & '.join(column), '\\\\')
diff --git a/expt_0501.cu b/expt_0501.cu
index 2d740e4..dcd25f5 100644
--- a/expt_0501.cu
+++ b/expt_0501.cu
@@ -1,5 +1,6 @@
// Experimental content: Test the correctness of binary search and special
// search
+#define ENABLE_SORT_TEST
#include "sortlib.cuh"
#include <algorithm>
diff --git a/expt_0503.cu b/expt_0503.cu
index 58f35aa..0ada96c 100644
--- a/expt_0503.cu
+++ b/expt_0503.cu
@@ -1,4 +1,5 @@
// Experimental content: Test branch performance
+#define ENABLE_SORT_TEST
#include "sortlib.cuh"
#include <algorithm>
@@ -59,8 +60,7 @@ __global__ void kernel(unsigned long step, const double slice_size,
// printf("%d\n", tid);
auto index = (int)(custom_sort.sample_cdf_custom_version(
- cudaSampleItem, cudaSampleItem + cuda_sample_length,
- cudaPopulationItem[tid]) /
+ cudaSampleItem, cudaPopulationItem[tid]) /
slice_size) -
1;
cdf_result[index] = true;
diff --git a/expt_0516.cu b/expt_0516.cu
index 351a8c4..48b3811 100644
--- a/expt_0516.cu
+++ b/expt_0516.cu
@@ -1,6 +1,6 @@
// Experimental content: Test branch performance (optimized memory and output)
// #define PRINT_READ_PROCESS
-#include "read_helper.h"
+#include "read_helper_p.h"
#include "sortlib.cuh"
#include <algorithm>
diff --git a/expt_0516_2.cu b/expt_0516_2.cu
index 860e146..9171d01 100644
--- a/expt_0516_2.cu
+++ b/expt_0516_2.cu
@@ -1,5 +1,6 @@
// Experimental content: Test CustomSort Calculation
#define DISABLE_TEST_WARNING
+#define ENABLE_SORT_TEST
#include "sortlib.cuh"
#include <algorithm>
diff --git a/expt_0520.cu b/expt_0520.cu
index bd1439f..42cdab3 100644
--- a/expt_0520.cu
+++ b/expt_0520.cu
@@ -202,14 +202,12 @@ int main(int argc, char **argv) {
}
auto error = cudaGetLastError();
- auto total_row = 0UL;
auto sample_length = strtol(argv[1], nullptr, 0);
auto insertion_length = strtol(argv[2], nullptr, 0);
printf("insert_length %ld, sample_length: %ld\n", insertion_length,
sample_length);
- ReadHelper reader("normal_distribution.txt", sample_length, insertion_length,
- total_row);
+ ReadHelper reader("normal_distribution.txt", sample_length, insertion_length);
reader.readFile();
key_type *cudaPopulation;
diff --git a/expt_0604.cu b/expt_0604.cu
new file mode 100644
index 0000000..bd64ad0
--- /dev/null
+++ b/expt_0604.cu
@@ -0,0 +1,73 @@
+// Experimental content: Print level by cdf
+
+#include "sortlib.cuh"
+#define READ_NO_OUTPUT
+#include "read_helper.h"
+
+long pow_for_sample(long n) {
+ auto x = 2;
+ for (int i = 1; i < n; i++) {
+ x *= 2;
+ }
+ return x - 1;
+}
+
+static unsigned trailing_zeroes(size_t index) {
+ constexpr auto block_size = 2;
+ unsigned bits = 0;
+ auto x = index / block_size;
+
+ if (x) {
+ while (x % block_size == 0) {
+ ++bits;
+ x /= block_size;
+ }
+ }
+ return bits;
+}
+
+inline double calcSliceSize(size_t insertion_size) {
+ return 1.0 / (double)insertion_size;
+}
+
+constexpr auto RESULT_LENGTH = 35;
+
+int main(int argc, char const *argv[]) {
+
+ if (argc != 3) {
+ printf("Usage %s [sample(pow)] [population]\n", argv[0]);
+ return 1;
+ }
+
+ auto sample_length = pow_for_sample(strtol(argv[1], nullptr, 10));
+ auto population_length = strtol(argv[2], nullptr, 10);
+
+ printf("sample length: %ld, population length: %ld\n", sample_length,
+ population_length);
+
+ ReadHelper readHelper("normal_distribution.txt", sample_length, 0);
+ readHelper.readFile();
+
+ std::vector<key_type> sample, population;
+ std::vector<unsigned int> result(RESULT_LENGTH);
+ readHelper.split_into(sample, population);
+ rebuildSort(sample);
+
+ auto scale_size = calcSliceSize(population_length);
+
+ auto sort = CustomSort(sample_length, sizeof(key_type) * 8);
+
+ for (auto element : readHelper.population_vector) {
+ auto ret = sort.sample_cdf_custom_version(sample.data(), element);
+ auto cdf_index = ret / scale_size;
+ auto index = trailing_zeroes((size_t)cdf_index);
+ result[index]++;
+ }
+
+ for (int i = 0; i < 32; i++) {
+ if (!result[i]) {
+ continue;
+ }
+ printf("%d: %d\n", i, result[i]);
+ }
+}
diff --git a/read_helper.h b/read_helper.h
index f8396f2..2256ef8 100644
--- a/read_helper.h
+++ b/read_helper.h
@@ -65,14 +65,14 @@ public:
return dst(mt19937);
}
- void readFile() {
+ bool readFile() {
this->population_vector.clear();
auto read_number = 0UL;
FILE *file = fopen(filename, "r");
if (file == nullptr) {
fprintf(stderr, "Unable to open file %s\n", filename);
- exit(1);
+ return false;
}
P_ERR("Reading sample");
@@ -98,6 +98,7 @@ public:
read_number++;
fclose(file);
P_ERR("\r");
+ return true;
}
void split_into(std::vector<key_type> &sample, std::vector<key_type> &p) {
diff --git a/read_helper_p.h b/read_helper_p.h
new file mode 100644
index 0000000..1b1d0eb
--- /dev/null
+++ b/read_helper_p.h
@@ -0,0 +1,111 @@
+
+#ifndef LOCKFREE_READ_HELPER_H
+#define LOCKFREE_READ_HELPER_H
+
+#include <cassert>
+#include <fstream>
+#include <random>
+#include <vector>
+
+#ifndef P_ERR
+#ifdef PRINT_READ_PROCESS
+#define P_ERR(...) fprintf(stderr, __VA_ARGS__)
+#else
+#define P_ERR(...)
+#endif
+#endif
+
+template <typename key_type> class ReadHelper {
+ // typedef unsigned long long key_type;
+
+ key_type max_value = std::numeric_limits<key_type>::min(),
+ min_value = std::numeric_limits<key_type>::max();
+
+ inline void store_into_vector(key_type value) {
+ if (max_value < value) {
+ max_value = value;
+ }
+ if (min_value > value) {
+ min_value = value;
+ }
+ population_vector.push_back(value);
+ }
+
+ char const *filename;
+ static constexpr size_t REVERSED_BLOCK = 256;
+
+ auto genRandomRow(size_t total_row) const {
+ if (total_row != 0) {
+ assert(total_row > (population_length + sample_length + REVERSED_BLOCK));
+ return randomRow(total_row - population_length - sample_length -
+ REVERSED_BLOCK);
+ }
+ return 0UL;
+ }
+
+public:
+ const size_t sample_length, population_length, random_number;
+ ReadHelper(char const *filename, size_t sample_length,
+ size_t population_length, size_t total_row = 0)
+ : filename(filename), sample_length(sample_length),
+ population_length(population_length),
+ random_number(genRandomRow(total_row)) {}
+ key_type maxValue() const { return max_value; }
+ key_type minValue() const { return min_value; }
+
+ std::vector<key_type> population_vector;
+
+ static unsigned long randomRow(unsigned long max_value_) {
+ std::random_device randomDevice;
+ std::mt19937 mt19937(randomDevice());
+ std::uniform_int_distribution<std::mt19937::result_type> dst(0, max_value_);
+ return dst(mt19937);
+ }
+
+ bool readFile() {
+ this->population_vector.clear();
+ auto read_number = 0UL;
+ std::ifstream fin(filename);
+
+ if (!fin.is_open()) {
+ return false;
+ }
+
+ for (key_type i; read_number < sample_length && !fin.eof();
+ store_into_vector(i)) {
+ fin >> i;
+ read_number++;
+ }
+
+ if (random_number > 0) {
+ read_number = random_number;
+ for (key_type i; read_number > 0 && !fin.eof(); fin >> i)
+ read_number--;
+ }
+
+ read_number = 0;
+
+ auto remain = population_length + REVERSED_BLOCK;
+ for (key_type i; read_number < remain && !fin.eof(); store_into_vector(i)) {
+ fin >> i;
+ read_number++;
+ }
+ fin.close();
+ return true;
+ }
+
+ void split_into(std::vector<key_type> &sample, std::vector<key_type> &p) {
+ sample.resize(sample_length - 2);
+ p.resize(population_length);
+ memcpy(sample.data(), population_vector.data(),
+ sizeof(key_type) * (sample_length - 2));
+ sample.push_back(this->max_value);
+ sample.push_back(this->min_value);
+ memcpy(p.data(), population_vector.data() + sample_length,
+ sizeof(key_type) * population_length);
+ }
+
+ size_t size() const { return this->population_vector.size(); }
+};
+
+#endif \ No newline at end of file
diff --git a/work.cu b/work_0719.cu
index 46bdfb4..46bdfb4 100644
--- a/work.cu
+++ b/work_0719.cu
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 16:17:25 +0000