102 lines
3.5 KiB
Plaintext
102 lines
3.5 KiB
Plaintext
ACED PROJECT
|
|
|
|
This repository is (part of) my work for the ``Arquitecturas de Elevado
|
|
Desempenho'' class. See the doc/proposal.pdf document for more information on
|
|
the problem statement.
|
|
|
|
|
|
[[Project Structure]]
|
|
|
|
root
|
|
├ aux Auxiliary scripts.
|
|
├ contrib External C libraries.
|
|
├ data Data for use as input or embedding in source.
|
|
├ doc Extra documentation related to the project.
|
|
├ includes Header files.
|
|
├ obj Compiled object files.
|
|
└ src Root project source files.
|
|
|
|
The directory is essentially a C project, with auxiliary documentation and
|
|
scripts. The main executable can be compiled by running the corresponding
|
|
[sane] recipe:
|
|
|
|
python3 make.py link
|
|
|
|
This will produce a DEBUG [main.debug.exe] executable in the root directory.
|
|
If a RELEASE environment variable is set, a RELEASE [main.release.exe]
|
|
executable is produced instead, i.e., to produce a release executable, run:
|
|
|
|
RELEASE=1 python3 make.py link
|
|
|
|
See all available recipes by running
|
|
|
|
python3 make.py --list
|
|
|
|
and read more about [sane]: at https://github.com/mikeevmm/sane.
|
|
|
|
|
|
[[Use Instructions]]
|
|
|
|
To use, pipe the input (structured according to the source specification) into
|
|
the executable, while specifying the number of outputs and inputs, in that
|
|
order, followed by a bin size (see the following section for details on the
|
|
meaning of the bin size). E.g.,
|
|
|
|
./main.release.exe 2 2 2 2 48 < data/2222_inq.txt
|
|
|
|
|
|
[[Notes on the Approach Taken]]
|
|
|
|
Originally, pairs were straightforwardly compared. This was too slow to tackle
|
|
even, for example [data/3332_inq.txt]. (Cf. [data/README].) So, instead, I'm now
|
|
trying a divide-and-conquer approach, now explained.
|
|
|
|
Consider the input to be N lines. From the ground truths, we know that the
|
|
number of non-equivalent rows, which we will denote k, is such that k << N.
|
|
So consider a subset of L lines (k << L < N). Without loss of generality, take
|
|
N/L to be an integer. For each subset L, at most k lines are non-equivalent.
|
|
We consider a "reduction" within each block, and then comparisons across
|
|
blocks: if there are P permutations to be considered (see [doc/proposal.pdf]
|
|
for details) this means, worst-case scenario, less than
|
|
|
|
(N/L)L²P + (N/2L)k²P + (N/4L)k²P + ... + (N/L)/2^log(N/L) k²P
|
|
= (N/L)L²P + (N/L)k²P(1 - L/N)
|
|
= NP[L + k²/L (1 - L/N)] (1)
|
|
|
|
operations. Compare this with the "straightforward" mode of operation, where
|
|
|
|
N²P (2)
|
|
|
|
operations are required. Clearly, the divide-and-conquer approach has an
|
|
advantage as long as the term in square brackets in (1) is significantly smaller
|
|
than N.
|
|
|
|
In pseudo-code:
|
|
|
|
block_size is provided
|
|
unique := []
|
|
sizes := []
|
|
|
|
base round:
|
|
# distribute loop
|
|
for block of rows of size block_size:
|
|
local_unique := unique rows in local block
|
|
push local_unique to unique
|
|
push len(local_unique) to sizes
|
|
|
|
reductions:
|
|
while len(sizes) > 1:
|
|
unique' := []
|
|
sizes' := []
|
|
|
|
# distribute loop
|
|
for pair of blocks in (unique, sizes): # Odd ones out are ignored
|
|
local := concatenation of pair of blocks
|
|
local_unique = unique rows in local
|
|
push local_unique to unique'
|
|
push len(local_unique) to sizes'
|
|
|
|
unique := unique'
|
|
sizes := sizes'
|
|
|
|
done |