Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Parallel random graph construction incorrect #10

Open
ehein6 opened this issue Apr 14, 2017 · 1 comment
Open

Parallel random graph construction incorrect #10

ehein6 opened this issue Apr 14, 2017 · 1 comment

Comments

@ehein6
Copy link

ehein6 commented Apr 14, 2017

Parallel random graph construction in GraphBIG is not implemented correctly.

C++ standard library containers like vector, list, and unordered_map are not thread-safe. Calling push_back concurrently on the same data structure without synchronization is leading to data corruption in this benchmark. Locking each vertex before adding an edge should solve the problem, but this will have a significant impact on performance.

See #7 for a demonstration of this issue.

@nailifeng
Copy link
Member

openG backend actually doesn't provide any thread-safe feature by design. The original design philosophy was that higher-level layers enforce the atomicity by themselves. That usually can offer better performance than blindly ensuring strong thread-safe at low-level because sometimes only higher-level code knows exactly when and what atomicity is required. This is also why each benchmark here has atomic-related code.

the parallel_randomgraph_construction function in graphconstruct.cpp was added by commit a25f419fbb8bdd383a74af49089746f78111c0cb, which was only for generating specific simulation traces. It was supposed to be used only when SIM flag is enabled. The SIM flag will enable some lock-based code in openG that ensures the atomicity (even though it is not an efficient implementation...).

Thanks a lot for pointing it out. I'll wrap the whole function with "#ifdef SIM" in the next commit to avoid confusions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants