xqgex / numa_black-box Goto Github PK
View Code? Open in Web Editor NEWBlack-box Concurrent Data Structures for NUMA Architectures
License: MIT License
Black-box Concurrent Data Structures for NUMA Architectures
License: MIT License
Black-box Concurrent Data Structures for NUMA Architectures Based on: http://cs.brown.edu/~irina/papers/asplos2017-final.pdf By: Irina Calciu, Siddhartha Sen, Mahesh Balakrishnan, Marcos K. Aguilera Node #1 Node #2 ╔═══════╦═══════╦═══════╦═══════╗ ╔═══════╦═══════╦═══════╦═══════╗ ║ Core ║ Core ║ Core ║ Core ┣━━━━┫ Core ║ Core ║ Core ║ Core ║ ╟───────╫───────╫───────╫───────╊━━━━╉───────╫───────╫───────╫───────╢ ║ Cache ║ Cache ║ Cache ║ Cache ┣━━━━┫ Cache ║ Cache ║ Cache ║ Cache ║ ╟───────╨───────╨───────╨───────╢ ╟───────╨───────╨───────╨───────╢ ║ Cache ║ ║ Cache ║ ╚═════════════┳━┳━┳═════════════╝ ╚═════════════┳━┳━┳═════════════╝ ┃ ┃ ┃ ┃ ┃ ┃ ┌─────────────┺━┻━┹─────────────┐ ┌─────────────┺━┻━┹─────────────┐ │ Memory │ │ Memory │ └───────────────────────────────┘ └───────────────────────────────┘ /************************************************************/ /************ My implementation *********************/ /************************************************************/ This is the general scheme of my implementation: ┌────────────────────────┐ │ libgenericDS │ ├────────────────────────┤ │ genericDataStructure.h │ │ genericDataStructure.c │ └────────────────────────┘ ▲ ║ Shared Memory ▼ ┌──────────────────────┐ ┌──────────────────┐ ┌────────────┐ │ libgenerateCommands │═══▶│ gds_commands.bin │═══▶│ libNUMAbb │ ├──────────────────────┤ └──────────────────┘ ├────────────┤ │ generateCommands.c │ │ NUMAbb.h │ │ │ │ NUMAbb.c │ └──────────────────────┘ └────────────┘ ▲ ▲ ║ ┌────────────┐ ║ ╚══════════════════│ myprogram │═════════════╝ ├────────────┤ │ main.c │ └────────────┘ The code was designed to work on unix system and was written in C. In order to run the program there is only one file that need to be run, But the files are still acting like a separate libraries. There is more work that need to be done, Feel free to fork my project. Run the program: Build and run the program by running the command: "sh makefile.sh" Limitation from the current implementation: 1) The mmap size is a limitaion on the amount of commands. 2) Variable MAX_CORES limit the program to work with up-to 512 cores. 3) Maximum 'op' and 'args' size is 1024 chars each. Problems: Unfortunately, My code isn't perfect yet, More upgrades that can be done: Section 5.2 To avoid small inefficient batches, the combiner in NR waits if the batch size is smaller than a parameter MIN BATCH. Rather than idle waiting, the combiner refreshes the local replica from the log, though it might need to refresh again after finally adding the batch to the log Section 5.5 - Better readers-writer lock The distributed readers-writer lock uses a per-reader lock to reduce reader overhead; the writer must acquire the locks from all readers. We modify this algorithm to reduce writer overhead as well, by adding an additional writer lock. To enter the critical section, the writer must acquire the writer lock and wait for all the readers locks to be released, without acquiring them; to exit, it releases its lock. A reader waits if the writer lock is taken, then acquires its local lock, and checks the writer lock again; if this lock is taken, the reader releases its local lock and restarts; otherwise, it enters the critical section; to exit, it releases the local lock. With this scheme, the writer and readers incur just one atomic write each on distinct cache lines to enter the critical sec- tion. Readers may starve if writers keep coming, but this is unlikely with NR , as often only one thread wishes to be a writer at a time (the combiner) and that thread has signif- icant work outside the critical section. Section 5.7 Padded the data and aligned the cache to avoid false sharing. General What prevent two combiners (on separate nodes) to write the log at the same time? I think there is need to create something that will prevent it. Build errors: In case of compilation errors, Make sure you have all the dependency packages on your computer, Use "apt-get install" / "yum install" / "dnf install" To install: (On Ubunto devel => dev) 1) libnuma-devel Development files for libnuma 2) numactl Library for tuning for Non Uniform Memory Access machines 3) numactl-libs libnuma libraries 4) numactl-devel Development package for building Applications that use numa 5) glibc-devel Object files for development using standard C libraries. 6) glibc-static C library static libraries for -static linking. 7) libstdc++-devel Header files and libraries for C++ development 8) libstdc++-static Static libraries for the GNU standard C++ library
@xqgex Thanks for the code & comments! A great complement to the original paper.
However my server can compile the program but always encounter either SIGSEGV or SIGABRT. Any possible fixes to that?
Best,
X.J.
[email protected]
CPU: 2 * Intel(R) Xeon(R) Gold 6240M CPU @ 2.60GHz
RAM: 6 * 32GB DDR4
OS: Ubuntu 18.04.3 LTS
GDB log:
(gdb) run
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /root/xuyangjin/NUMA_Black-Box-master/myprogram
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Analyzing your machine...
Nodes (physical cpu's): 2
Cores per node: 36
Hyperthreading: ON
Example:
Node #1 Node #2
╔═══════╦═══════╦═══════╦═══════╗ ╔═══════╦═══════╦═══════╦═══════╗
║ Core ║ Core ║ Core ║ Core ┣━━━━┫ Core ║ Core ║ Core ║ Core ║
╟───────╫───────╫───────╫───────╊━━━━╉───────╫───────╫───────╫───────╢
║ Cache ║ Cache ║ Cache ║ Cache ┣━━━━┫ Cache ║ Cache ║ Cache ║ Cache ║
╟───────╨───────╨───────╨───────╢ ╟───────╨───────╨───────╨───────╢
║ Cache ║ ║ Cache ║
╚═════════════┳━┳━┳═════════════╝ ╚═════════════┳━┳━┳═════════════╝
┃ ┃ ┃ ┃ ┃ ┃
┌─────────────┺━┻━┹─────────────┐ ┌─────────────┺━┻━┹─────────────┐
│ Memory │ │ Memory │
└───────────────────────────────┘ └───────────────────────────────┘
Press Any Key to Start Simulation
[New Thread 0x7ffff77c4700 (LWP 57725)]
[New Thread 0x7ffff6fc3700 (LWP 57726)]
[New Thread 0x7ffff67c2700 (LWP 57730)]
[New Thread 0x7ffff5fc1700 (LWP 57731)]
[New Thread 0x7ffff57c0700 (LWP 57732)]
[New Thread 0x7ffff4fbf700 (LWP 57733)]
[New Thread 0x7fff9ffff700 (LWP 57734)]
[New Thread 0x7fff9f7fe700 (LWP 57735)]
[New Thread 0x7fff9effd700 (LWP 57736)]
[New Thread 0x7fff9e7fc700 (LWP 57737)]
[New Thread 0x7fff9dffb700 (LWP 57738)]
[New Thread 0x7fff9d7fa700 (LWP 57739)]
[New Thread 0x7fff9cff9700 (LWP 57740)]
[New Thread 0x7fff7bfff700 (LWP 57741)]
Thread 4 "myprogram" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7ffff67c2700 (LWP 57730)]
0x0000555555558671 in appendToLog (n=12, batch=0x7fffaa802d58) at NUMAbb.c:737
737 strcpy(loopEntry->op,batch[i]->slot.op);
(gdb) run
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /root/xuyangjin/NUMA_Black-Box-master/myprogram
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Analyzing your machine...
Nodes (physical cpu's): 2
Cores per node: 36
Hyperthreading: ON
Example:
Node #1 Node #2
╔═══════╦═══════╦═══════╦═══════╗ ╔═══════╦═══════╦═══════╦═══════╗
║ Core ║ Core ║ Core ║ Core ┣━━━━┫ Core ║ Core ║ Core ║ Core ║
╟───────╫───────╫───────╫───────╊━━━━╉───────╫───────╫───────╫───────╢
║ Cache ║ Cache ║ Cache ║ Cache ┣━━━━┫ Cache ║ Cache ║ Cache ║ Cache ║
╟───────╨───────╨───────╨───────╢ ╟───────╨───────╨───────╨───────╢
║ Cache ║ ║ Cache ║
╚═════════════┳━┳━┳═════════════╝ ╚═════════════┳━┳━┳═════════════╝
┃ ┃ ┃ ┃ ┃ ┃
┌─────────────┺━┻━┹─────────────┐ ┌─────────────┺━┻━┹─────────────┐
│ Memory │ │ Memory │
└───────────────────────────────┘ └───────────────────────────────┘
Press Any Key to Start Simulation
[New Thread 0x7ffff77c4700 (LWP 57743)]
[New Thread 0x7ffff6fc3700 (LWP 57744)]
[New Thread 0x7ffff67c2700 (LWP 57745)]
[New Thread 0x7ffff5fc1700 (LWP 57746)]
[New Thread 0x7ffff57c0700 (LWP 57747)]
[New Thread 0x7ffff4fbf700 (LWP 57748)]
[New Thread 0x7fff9ffff700 (LWP 57749)]
[New Thread 0x7fff9f7fe700 (LWP 57750)]
[New Thread 0x7fff9effd700 (LWP 57751)]
[New Thread 0x7fff9e7fc700 (LWP 57752)]
[New Thread 0x7fff9dffb700 (LWP 57753)]
[New Thread 0x7fff9d7fa700 (LWP 57754)]
[New Thread 0x7fff9cff9700 (LWP 57755)]
[New Thread 0x7fff7bfff700 (LWP 57756)]
myprogram: ../nptl/pthread_mutex_lock.c:79: __pthread_mutex_cond_lock: Assertion `mutex->__data.__owner == 0' failed.
[New Thread 0x7fff7b7fe700 (LWP 57757)]
Thread 8 "myprogram" received signal SIGABRT, Aborted.
[Switching to Thread 0x7fff9ffff700 (LWP 57749)]
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
51 ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.