Synchronization (computer science): Difference between revisions

Revision as of 05:46, 6 January 2025

Latest revision as of 10:05, 20 August 2025

(7 intermediate revisions by 6 users not shown)

Line 34:

==Minimization==

One of the challenges for exascale algorithm design is to minimize or reduce synchronization.

Synchronization takes more time than computation, especially in distributed computing. Reducing synchronization drew attention from computer scientists for decades. Whereas it becomes an increasingly significant problem recently as the gap between the improvement of computing and latency increases. Experiments have shown that (global) communications due to synchronization on distributed computers takes a dominated share in a sparse iterative solver.<ref>{{cite journal|title=Minimizing synchronizations in sparse iterative solvers for distributed supercomputers |author=Shengxin, Zhu and Tongxiang Gu and Xingping Liu|journal=Computers & Mathematics with Applications|volume=67|issue=1|pages=199–209|year=2014|doi=10.1016/j.camwa.2013.11.008|doi-access=free|hdl=10754/668399|hdl-access=free}}</ref> This problem is receiving increasing attention after the emergence of a new benchmark metric, the High Performance Conjugate Gradient (HPCG),<ref>{{cite web|url=http://hpcg-benchmark.org/|title=HPCG Benchmark}}</ref> for ranking the top 500 supercomputers.

==Problems==

Line 64:

==Implementation==

===SpinlockSpinlocks===

{{Main article|Spinlock}}

Another effective way of implementing synchronization is by using spinlocks. Before accessing any shared resource or piece of code, every processor checks a flag. If the flag is reset, then the processor sets the flag and continues executing the thread. But, if the flag is set (locked), the threads would keep spinning in a loop and keep checking if the flag is set or not. But, spinlocksSpinlocks are effective only if the flag is reset for lower cycles; otherwise, it can lead to performance issues as it wastes many processor cycles waiting.<ref>{{Cite book|title=Embedded Software Development with ECos|last=Massa|first=Anthony|publisher=Pearson Education Inc|year=2003|isbn=0-13-035473-2}}</ref>

===Barriers===

Line 72:

Barriers are simple to implement and provide good responsiveness. They are based on the concept of implementing wait cycles to provide synchronization. Consider three threads running simultaneously, starting from barrier 1. After time t, thread1 reaches barrier 2 but it still has to wait for thread 2 and 3 to reach barrier2 as it does not have the correct data. Once all the threads reach barrier 2 they all start again. After time t, thread 1 reaches barrier3 but it will have to wait for threads 2 and 3 and the correct data again.

Thus, in barrier synchronization of multiple threads there will always be a few threads that will end up waiting for other threads as in the above example thread 1 keeps waiting for thread 2 and 3. This results in severe degradation of the process performance.<ref name=":0">{{Citecite journal|last=Meng,book Chen, Pan, Yao, Wu|first doi=Jinglei, Tianzhou, Ping, Jun10.1109/HPCC.2014.148 Minghui|date=2014|title chapter=A speculativeSpeculative mechanismMechanism for barrierBarrier Synchronization sychronization|journal title=2014 IEEE InternationalIntl ConferenceConf on High Performance Computing and Communications (HPCC), 2014 IEEE 6th InternationalIntl SymposiumSymp on Cyberspace Safety and Security (CSS) and, 2014 IEEE 11th InternationalIntl ConferenceConf on Embedded Software and SystemsSyst (HPCC,CSS,ICESS) | date=2014 | last1=Meng | first1=Jinglei | last2=Chen | first2=Tianzhou | last3=Pan | first3=Ping | last4=Yao | first4=Jun | last5=Wu | first5=Minghui | pages=858–865 | isbn=978-1-4799-6123-8 }}</ref>

The barrier synchronization wait function for i^th thread can be represented as: