Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Kết hợp chờ có giới hạn: xây dựng các đối tượng chia sẻ robust và có thông lượng cao
Tóm tắt
Các bộ đếm chia sẻ là một trong những cấu trúc phối hợp cơ bản nhất trong tính toán phân tán. Các triển khai bộ đếm chia sẻ hiện có đều hoặc làm tắc nghẽn, không tuần tự hóa hoặc có điểm nút tuần tự. Chúng tôi trình bày thuật toán bộ đếm đầu tiên vừa tuần tự hóa, vừa không chặn, và có thể đạt được thông lượng cao trong các thực thi đồng bộ k — các thực thi mà tốc độ quá trình thay đổi với hệ số cố định tối đa k. Thuật toán dựa trên một biến thể mới lạ của mô hình kết hợp phần mềm mà chúng tôi gọi là kết hợp chờ có giới hạn (BWC). Do đó, nó có thể được sử dụng để đạt được các triển khai, sở hữu cùng những thuộc tính, của bất kỳ đối tượng nào hỗ trợ các thao tác có thể kết hợp, chẳng hạn như ngăn xếp hoặc hàng đợi. Khác với các thuật toán kết hợp trước đó, nơi mà các quá trình có thể phải chờ đợi nhau một cách vô thời hạn, trong thuật toán BWC, một quá trình chỉ chờ đợi các quá trình khác trong một khoảng thời gian có giới hạn và sau đó “nắm lấy vận mệnh vào tay mình”. Để lý luận chặt chẽ về tính song song có thể đạt được bởi thuật toán của chúng tôi, chúng tôi định nghĩa một chỉ số mới để đo lường thông lượng của các đối tượng chia sẻ, mà chúng tôi tin là thú vị theo đúng nghĩa của nó. Chúng tôi sử dụng chỉ số này để chứng minh rằng thuật toán của chúng tôi đạt được thông lượng Ω(N/ log N) trong các thực thi đồng bộ k, trong đó N là số lượng quá trình có thể tham gia vào thuật toán. Thuật toán của chúng tôi sử dụng hai công cụ mà chúng tôi tin có thể hữu ích để có được triển khai không chặn có độ song song cao cho các đối tượng bổ sung. Thứ nhất là "khóa đồng bộ", các khóa mà chỉ được tôn trọng bởi các quá trình trong các thực thi đồng bộ k và không được quan tâm đến trong trường hợp khác; thứ hai là "giao dịch giả" - một sự yếu hóa của giao dịch thông thường cho phép tính song song cao hơn.
Từ khóa
#bộ đếm chia sẻ #thuật toán không chặn #kết hợp chờ có giới hạn #thông lượng #tính toán phân tánTài liệu tham khảo
Aspnes J., Herlihy M., Shavit N.: Counting networks. J. ACM 41(5), 1020–1048 (1994)
Attiya H., Dagan A.: Improved implementations of binary universal operations. J. ACM 48(5), 1013–1037 (2001)
Attiya, H., Guerraoui, R., Kouznetsov, P.: Computing with reads and writes in the absence of step contention. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC’05) (2005)
Dwork C., Herlihy M., Waarts O.: Contention in shared memory algorithms. J. ACM 44(6), 779–805 (1997)
Ellen, F., Lev, Y., Luchangco, V., Moir, M.: Snzi: scalable nonzero indicators. In: Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2007)
Fich, F.E., Hendler, D., Shavit, N.: Linear lower bounds on real-world implementations of concurrent objects. In: Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS) (2005)
Goodman, J.R., Vernon, M.K., Woest, P.J.: Efficent synchronization primitives for large-scale cache-coherent multiprocessors. In: ASPLOS, pp. 64–75 (1989)
Gottlieb, A., Grishman, R., Kruskal, C.P., McAuliffe, K.P., Rudolph, L., Snir, M.: The nyu ultracomputer designing a mimd, shared-memory parallel machine. In: ISCA ’98: 25 years of the international symposia on Computer architecture (selected papers), pp. 239–254, New York, NY, USA. ACM Press, New York (1998)
Greenwald, M.: Two-handed emulation: how to build non-blocking implementations of complex data-structures using dcas. In: PODC ’02: Proceedings of the twenty-first annual symposium on Principles of distributed computing, pp. 260–269, New York, NY, USA. ACM Press, New York (2002)
Ha, P.H., Papatriantafilou, M., Tsigas, P.: Self-tuning reactive distributed trees for counting and balancing. In: OPODIS, pp. 213–228 (2004)
Hendler, D., Kutten, S.: Bounded-wait combining: Constructing robust and high-throughput shared objects. In: Proceedings of the 20th International Symposium on Distributed Computing (DISC’06), pp. xx–xx (2006)
Hendler, D., Shavit, N., Yerushalmi, L.: A scalable lock-free stack algorithm. In: SPAA ’04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pp. 206–215, New York, NY, USA. ACM Press, New York (2004)
Herlihy M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)
Herlihy M.: A methodology for implementing highly concurrent objects. ACM Trans. Program. Lang. Syst. 15(5), 745–770 (1993)
Herlihy M., Shavit N., Waarts O.: Linearizable counting networks. Distributed Comput. 9(4), 193–203 (1996)
Herlihy M., Wing J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)
Kruskal C.P., Rudolph L., Snir M.: Efficient synchronization on multiprocessors with shared memory. ACM Trans. Program. Lang. Syst. 10(4), 579–601 (1988)
Moir, M., Nussbaum, D., Shalev, O., Shavit, N.: Using elimination to implement scalable and lock-free fifo queues. In: SPAA’05: Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures, pp. 253–262, NY, USA. ACM Press, New York (2005)
Shavit N., Zemach A.: Diffracting trees. ACM Trans. Comput. Syst. 14(4), 385–428 (1996)
Shavit N., Zemach A.: Combining funnels: a dynamic approach to software combining. J. Parallel Distributed Comput. 60(11), 1355–1387 (2000)
Wattenhofer R., Widmayer P.: The counting pyramid: an adaptive distributed counting scheme. J. Parallel Distributed Comput. 64(4), 449–460 (2004)
Yew P.-C., Tzeng N.-F., Lawrie D.H.: Distributing hot-spot addressing in large-scale multiprocessors. IEEE Trans. Comput. 36(4), 388–395 (1987)