Patent ID: 9218307
Filing Date: 2015-12-22
Classification: G06F

Abstract:
1. A method of operation in a computer system having multiple processors operatively coupled to a memory, said memory including a computer useable medium tangibly embodying at least one program of instructions executable by said processor to perform operations representing said method, said operations comprising: implementing a data synchronization mechanism for synchronizing access to shared data stored in said memory by readers and writers of said data that execute on said processors, said synchronization mechanism requiring said writers to periodically perform a distributed synchronization operation with respect to a plurality of said processors or plural threads of execution running on said processors; establishing in said memory a hierarchical tree data structure having a set of nodes that includes a root node, one or more levels of internal nodes and a plurality of leaf nodes, there being a leaf node for each of said processors or threads used by said writers to perform said synchronization operation, and each of said leaf nodes, said internal nodes and said root node storing an identifier that associates said node with one of said processors or with one of said threads, said nodes being interconnected by links that establish parent-child relationships between said nodes such that said hierarchical tree data structure is traversable from said root node through said internal nodes to reach said leaf nodes; parallelizing said synchronization operation by traversing said nodes from said root node to a lowest level of said internal nodes and performing the following node processing for each node: said node processing being continued until said synchronization operation has been performed with respect all processors or threads associated with said leaf nodes.