Concurrent data structures are becoming more and more popular in parallel computing as they are widely used in operating systems and concurrent programming. There are two types of algorithms to implement the concurrent data structures: blocking and non-blocking. Blocking algorithms are essentially lock-based algorithms which allow the sequential order for processes to complete operations on the shared data structures. However, on the asynchronous multiprocessor systems when there are more numbers of threads than numbers of cores, they suffer huge performance degradation as the result of scheduling preemption, cache misses and page faults etc. Non-blocking algorithms could tolerate those problems and potentially achieve high concurrency while maintaining low overhead, so they are more robust in the multithreaded programming models. Reservoir Simulations play a crucial role in oil and gas industry, and high concurrency and parallelization of numerical calculations without significant performance degradation in the multiprocessor systems are becoming urgent for large-scale reservoir simulations. Here we implement our new non-blocking algorithm for concurrent data structures (FIFO queues etc.) used for solving the discrete linear equation system (the discrete energy and mass balance equations) on the IBM Power7 with up to 128 threads. The results show that our new designed non-blocking algorithm could enhance the performance of the parallel program on both of the systems with dedicated processors and with multiprogrammed processors. Our research shows that there are significant potential applications of the non-blocking concurrent data structures on the high performance computing in oil and gas industry.
