UMAP-APPS¶

This repository contains applications that use the umap library to manage large regions of memory for them.

Take a look at our Getting Started guide for all you need to get up and running.

Getting Started¶

Dependencies¶

At a minimum, the programs under umap-apps depend cmake 3.5.1 or greater and upon umap being installed.

Follow the instructions for installing umap from the umap repository located here.

Umap-apps Build and Installation¶

Once the prerequisites are taken care of, the following lines should get you up and running:

$ git clone https://github.com/LLNL/umap-apps.git
$ mkdir build && cd build
$ cmake -DUMAP_INSTALL_PATH="<path to where umap is installed>" ../umap-apps
$ make

By default, umap-apps will build a Release type build and will use the system defined directories for installation. To specify different build types or specify alternate installation paths, see the Advanced Configuration.

Should you wish to also install the applications in their respective installation directories, type:

$ make install

Umap-apps installs files to the lib, include and bin directories of the CMAKE_INSTALL_PREFIX.

Advanced Configuration¶

Listed below are the umap-specific options which may be used when configuring your build directory with cmake. Some CMake-specific options have also been added to show how to make additional changes to the build configuration.

cmake -DUMAP_INSTALL_PATH="<path to where umap is installed>"

Here is a summary of the configuration options, their default value, and meaning:

Variable Default Meaning

UMAP_INSTALL_PATH not set Location of umap

CFITS_LIBRARY_PATH not set Location of cfitsio library

CFITS_INCLUDE_PATH not set Location of cfitsio include files

CMAKE_CXX_COMPILER not set C++ compiler to use

DCMAKE_CC_COMPILER not set C compiler to use

These arguments are explained in more detail below:

UMAP_INSTALL_PATH Location of prerequisite umap installation.
CFITS_INCLUDE_PATH and CFITS_LIBRARY_PATH If these are specified, then the applications that use FITS files as the backing store for umap() will be built.

BFS README¶

## Generate edge list using a R-MAT generator ``` ./rmat_edge_generator/generate_edge_list

-o [out edge list file name (required)]

-s [seed for random number generator; default is 123]

-v [SCALE; The logarithm base two of the number of vertices; default is 17]

-e [#of edges; default is 2^{SCALE} x 16]

-a [initiator parameter A; default is 0.57]

-b [initiator parameter B; default is 0.19]

-c [initiator parameter C; default is 0.19]

-r [if true, scrambles edge IDs; default is true]

-u [if true, generates edges for the both direction; default is true] ```

As for the initiator parameters,

see [Graph500, 3.2 Detailed Text Description](https://graph500.org/?page_id=12#sec-3_2) for more details.

#### Generate Graph 500 inputs ` ./generate_edge_list -o /mnt/ssd/edge_list -v 20 -e $((2**20*16)) `` This command generates a edge list file (/mnt/ssd/edge_list) which contains the edges of a SCALE 20 graph. In Graph 500, the number of edges of a graph is #vertives x 16 (16 is called ‘edge factor’).

## Ingest Edge List (construct CSR graph) ` ./ingest_edge_list -g /l/ssd/csr_graph_file /l/ssd/edgelist1 /l/ssd/edgelist2 `

Load edge data from files /l/ssd/edgelist1 and /l/ssd/edgelist2 (you can specify an arbitrary number of files).

A CSR graph is constructed in /l/ssd/csr_graph_file. * Each line of input files must be a pair of source and destination vertex IDs (unsigned 64bit number). * This program treats inputs as a directed graph, that is, it does not ingest edges for both directions. * This is a multi-threads (OpenMP) program. You can control the number of threads using the environment variable OMP_NUM_THREADS. * As for real-world datasets, [SNAP Datasets](http://snap.stanford.edu/data/index.html) is popular in the graph processing community. Please note that some datasets in SNAP are a little different. For example, the first line is a comment; you have to delete the line before running this program.

## Run BFS ` ./run_bfs -n \[#of vertices\] -m \[#of edges\] -g \[/path/to/graph_file\] `

You can get #of vertices and #of edges by running ingest_edge_list.
This is a multi-threads (OpenMP) program.

You can control the number of threads using the environment variable OMP_NUM_THREADS.

API¶

Class Hierarchy¶

- Namespace median
  - Template Struct cube_t
- Namespace utility
  - Namespace utility::umap_fits_file
    - Struct Cube
    - Struct Tile_Dim
    - Struct Tile_File
    - Class CfitsStoreFile
    - Class Tile
  - Struct umt_optstruct_t
- Struct options_t
- Struct rmat_option_t
- Struct vector_t
- Class beta_distribution
- Class pageiotest
- Class rmat_edge_generator
  - Class rmat_edge_generator::input_iterator_type
- Template Class vector_iterator

File Hierarchy¶

- Directory bfs
  - Directory generator
    - File generate_edge_list.cpp
    - File hash.hpp
    - File rmat_edge_generator.hpp
  - File bfs_kernel.hpp
  - File compute_degree_distribution.cpp
  - File ingest_edge_list.cpp
  - File README.md
  - File run_bfs.cpp
  - File test_bfs.cpp
- Directory churn
  - File churn.cpp
  - File options.cpp
  - File options.h
- Directory calculation
  - File INSTRUCTION.md
  - File run_random_vector.cpp
  - File test_median_calculation.cpp
  - File torben.hpp
  - File utility.hpp
  - File vector.hpp
- Directory pfbenchmark
  - File nvmebenchmark.cpp
  - File pfbenchmark.cpp
- Directory umapcpu
  - File umapcpu.cpp
- Directory umapsort
  - File umapsort.cpp
- Directory utility
  - File bitmap.hpp
  - File commandline.hpp
  - File file.hpp
  - File mmap.hpp
  - File time.hpp
  - File umap_file.hpp
  - File umap_fits_file.hpp

Full API¶

Namespaces¶

Namespace bfs¶

Contents

Functions
Variables

Functions¶

Variables¶

Variable bfs::k_infinite_level

Namespace chrono¶

Namespace median¶

Contents

Classes
Functions

Classes¶

Template Struct cube_t

Functions¶

Namespace rmat_edge_generator_detail¶

Contents

Functions

Functions¶

Namespace std¶

STL namespace.

Namespace utility¶

Contents

Namespaces
Classes
Functions
Variables

Namespaces¶

Namespace utility::umap_fits_file

Classes¶

Struct umt_optstruct_t

Variables¶

Namespace utility::umap_fits_file¶

Contents

Classes
Functions
Variables

Classes¶

Functions¶

Variables¶

Variable utility::umap_fits_file::Cubes

Classes and Structs¶

Template Struct cube_t¶

Defined in File utility.hpp

Struct Documentation¶

template <typename _pixel_type> struct cube_t¶

Public Types

template<> using pixel_type = _pixel_type¶

Public Members

size_t size_x¶

size_t size_y¶

size_t size_k¶

pixel_type *data¶

Struct options_t¶

Defined in File options.h

Struct Documentation¶

struct options_t¶

Public Members

int iodirect¶

int usemmap¶

int initonly¶

int noinit¶

uint64_t page_buffer_size¶

uint64_t num_churn_pages¶

uint64_t num_load_pages¶

uint64_t num_churn_threads¶

uint64_t num_load_reader_threads¶

uint64_t num_load_writer_threads¶

char const *fn¶

uint64_t testduration¶

Struct rmat_option_t¶

Defined in File generate_edge_list.cpp

Struct Documentation¶

struct rmat_option_t¶

Public Members

uint64_t seed = {123}¶

uint64_t vertex_scale = {17}¶

uint64_t edge_count = {(1ULL << 17) * 16}¶

double a = {0.57}¶

double b = {0.19}¶

double c = {0.19}¶

bool scramble_id = {true}¶

bool generate_both_directions = {true}¶

Struct Cube¶

Defined in File umap_fits_file.hpp

Struct Documentation¶

struct Cube¶

Public Members

size_t tile_size¶

size_t cube_size¶

off_t page_size¶

vector<utility::umap_fits_file::Tile> tiles¶

Struct Tile_Dim¶

Defined in File umap_fits_file.hpp

Struct Documentation¶

struct Tile_Dim¶

Public Members

std::size_t xDim¶

std::size_t yDim¶

std::size_t elem_size¶

Struct Tile_File¶

Defined in File umap_fits_file.hpp

Struct Documentation¶

struct Tile_File¶

Public Members

int fd¶

std::string fname¶

std::size_t tile_start¶

std::size_t tile_size¶

Struct umt_optstruct_t¶

Defined in File commandline.hpp

Struct Documentation¶

struct umt_optstruct_t¶

Public Members

int initonly¶

int noinit¶

int usemmap¶

int shuffle¶

long pagesize¶

uint64_t numpages¶

uint64_t numthreads¶

uint64_t bufsize¶

uint64_t uffdthreads¶

uint64_t pages_to_access¶

char const *filename¶

char const *dirname¶

Struct vector_t¶

Defined in File vector.hpp

Struct Documentation¶

struct vector_t¶

Public Members

double x_intercept¶

double x_slope¶

double y_intercept¶

double y_slope¶

Class beta_distribution¶

Defined in File run_random_vector.cpp

Class Documentation¶

class beta_distribution¶

Public Functions

beta_distribution(double a, double b)¶

template <typename rnd_engine> double operator()(rnd_engine &engine)¶

Class pageiotest¶

Defined in File churn.cpp

Class Documentation¶

class pageiotest¶

Public Functions

pageiotest(int _ac, char **_av)¶

~pageiotest(void)¶

void start(void)¶

void run(void)¶

void stop(void)¶

Class rmat_edge_generator¶

Defined in File rmat_edge_generator.hpp

Nested Relationships¶

Nested Types¶

Class rmat_edge_generator::input_iterator_type

Class Documentation¶

class rmat_edge_generator¶

RMAT edge generator, based on Boost Graph’s RMAT generator

Options include scrambling vertices based on a hash funciton, and symmetrizing the list. Generated edges are not sorted. May contain duplicate and self edges.

Public Types

typedef uint64_t vertex_descriptor¶

typedef std::pair<uint64_t, uint64_t> value_type¶

typedef value_type edge_type¶

Public Functions

rmat_edge_generator(uint64_t seed, uint64_t vertex_scale, uint64_t edge_count, double a, double b, double c, double d, bool scramble, bool undirected)¶: seed used to be 5489

input_iterator_type begin()¶: Returns the begin of the input iterator.

input_iterator_type end()¶: Returns the end of the input iterator.

void sanity_max_vertex_id()¶

uint64_t max_vertex_id()¶

size_t size()¶

Protected Functions

edge_type generate_edge()¶: Generates a new RMAT edge. This function was adapted from the Boost Graph Library.

edge_type generate_edge(std::mt19937 &rng, std::uniform_real_distribution<> &dis)¶

Protected Attributes

const uint64_t m_seed¶

std::mt19937 m_rng¶

std::uniform_real_distribution m_dis¶

const uint64_t m_vertex_scale¶

const uint64_t m_edge_count¶

const bool m_scramble¶

const bool m_undirected¶

const double m_rmat_a¶

const double m_rmat_b¶

const double m_rmat_c¶

const double m_rmat_d¶

class input_iterator_type : public std::iterator<std::input_iterator_tag, edge_type, ptrdiff_t, const edge_type *, const edge_type&>¶

InputIterator class for rmat_edge_generator.

Public Functions

input_iterator_type(rmat_edge_generator *ptr_rmat, uint64_t count)¶

const edge_type &operator*() const¶

input_iterator_type &operator++()¶

input_iterator_type operator++(int)¶

edge_type *operator->()¶

bool is_equal(const input_iterator_type &_x) const¶

Friends

bool operator==(const input_iterator_type &x, const input_iterator_type &y)¶: Return true if x and y are both end or not end, or x and y are the same.

bool operator!=(const input_iterator_type &x, const input_iterator_type &y)¶: Return false if x and y are both end or not end, or x and y are the same.

Class rmat_edge_generator::input_iterator_type¶

Defined in File rmat_edge_generator.hpp

Nested Relationships¶

This class is a nested type of Class rmat_edge_generator.

Inheritance Relationships¶

Base Type¶

public std::iterator< std::input_iterator_tag, edge_type, ptrdiff_t, const edge_type *, const edge_type & >

Class Documentation¶

class input_iterator_type : public std::iterator<std::input_iterator_tag, edge_type, ptrdiff_t, const edge_type *, const edge_type&>

InputIterator class for rmat_edge_generator.

Public Functions

input_iterator_type(rmat_edge_generator *ptr_rmat, uint64_t count)

const edge_type &operator*() const

input_iterator_type &operator++()

input_iterator_type operator++(int)¶

edge_type *operator->()

bool is_equal(const input_iterator_type &_x) const

Friends

bool operator==(const input_iterator_type &x, const input_iterator_type &y): Return true if x and y are both end or not end, or x and y are the same.

bool operator!=(const input_iterator_type &x, const input_iterator_type &y): Return false if x and y are both end or not end, or x and y are the same.

Class CfitsStoreFile¶

Defined in File umap_fits_file.hpp

Inheritance Relationships¶

Base Type¶

public Store

Class Documentation¶

class CfitsStoreFile : public Store¶

Public Functions

CfitsStoreFile(Cube *_cube_, size_t _rsize_, size_t _alignsize_)¶

~CfitsStoreFile()¶

ssize_t read_from_store(char *buf, size_t nb, off_t off)¶

ssize_t write_to_store(char *buf, size_t nb, off_t off)¶

Public Members

void *region¶

Class Tile¶

Defined in File umap_fits_file.hpp

Class Documentation¶

class Tile¶

Public Functions

Tile(const std::string &_fn)¶

ssize_t pread(std::size_t alignment, void *cpy_buf, void *buf, std::size_t nbytes, off_t offset)¶

Tile_Dim get_Dim()¶

Template Class vector_iterator¶

Defined in File vector.hpp

Class Documentation¶

template <typename pixel_type> class vector_iterator¶

Public Types

template<> using value_type = pixel_type¶

template<> using difference_type = ssize_t¶

template<> using iterator_category = std::random_access_iterator_tag¶

template<> using pointer = value_type *¶

template<> using reference = value_type&¶

Public Functions

vector_iterator(const median::cube_t<pixel_type> &_cube, const vector_t &_vector, const size_t _start_pos)¶

vector_iterator(const vector_iterator&)¶

bool operator==(const vector_iterator &other)¶

bool operator!=(const vector_iterator &other)¶

difference_type operator-(const vector_iterator &other)¶

value_type operator*()¶

vector_iterator &operator++()¶

Public Static Functions

static vector_iterator create_end(const median::cube_t<pixel_type> &cube, const vector_t &vector)¶

Functions¶

Function bfs::init_bfs¶

Defined in File bfs_kernel.hpp

Function Documentation¶

void bfs::init_bfs(const size_t num_vertices, uint16_t *const level, uint64_t *visited_filter)¶

initialize variables to run BFS

Parameters

num_vertices: The number of veritces
level: A pointer of level array
A: pointer to an bitset for visited filter

Function bfs::run_bfs¶

Defined in File bfs_kernel.hpp

Function Documentation¶

uint16_t bfs::run_bfs(const size_t num_vertices, const uint64_t *const index, const uint64_t *const edges, uint16_t *const level, uint64_t *visited_filter)¶

BFS kernel. This kernel runs with OpenMP. In order to simplify the implementation of this kernel, some operations are not designed to avoid race conditions as long as they are consistent with the correct status.

Parameters

num_vertices: The number of vertices
index: A pointer of an index array
edges: A pointer of an edges array
level: A pointer of level array
visited_filter: A pointer of an bitset for visited filter

Function check_edge_list¶

Defined in File ingest_edge_list.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “check_edge_list” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function count_level¶

Defined in File run_bfs.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “count_level” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function cpu_setcpu¶

Defined in File umapcpu.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “cpu_setcpu” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function do_read_modify_write_pages¶

Defined in File pfbenchmark.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “do_read_modify_write_pages” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function do_read_pages(uint64_t)¶

Defined in File nvmebenchmark.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “do_read_pages” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function do_read_pages(uint64_t, uint64_t)¶

Defined in File pfbenchmark.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “do_read_pages” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function do_write_pages(uint64_t)¶

Defined in File nvmebenchmark.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “do_write_pages” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function do_write_pages(uint64_t, uint64_t)¶

Defined in File pfbenchmark.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “do_write_pages” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function find_bfs_root¶

Defined in File run_bfs.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “find_bfs_root” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Template Function get_index¶

Defined in File vector.hpp

Function Documentation¶

template <typename pixel_type> ssize_t get_index(const median::cube_t<pixel_type> &cube, const vector_t &vec, const size_t epoch): Returns an index of a 3D coordinate. vector version.

Function getns(void)¶

Defined in File umapcpu.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “getns” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function getns(void)¶

Defined in File umapsort.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “getns” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function getoptions(options_t&, int&, char **)¶

Defined in File options.cpp

Function Documentation¶

void getoptions(options_t&, int&, char **argv)¶

Function getoptions(options_t&, int&, char **)¶

Defined in File options.h

Function Documentation¶

void getoptions(options_t&, int&, char **argv)

Function ingest_edges¶

Defined in File ingest_edge_list.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “ingest_edges” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function initdata(uint64_t *, int64_t)¶

Defined in File umapcpu.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “initdata” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/

Function initdata(uint64_t *, uint64_t)¶

Defined in File umapsort.cpp

Function Documentation¶

Warning

doxygenfunction: Cannot find function “initdata” in doxygen xml output for project “umap-apps” from directory: ../doxygen/xml/