کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431449 688550 2015 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A load balanced directory for distributed shared memory objects
ترجمه فارسی عنوان
دایرکتوری تعادل بار برای اشیاء توزیع شده به اشتراک گذاشته شده
کلمات کلیدی
سیستم های توزیع شده، دایرکتوری توزیع شده، جسم مشترک، کشش-انسجام، شبکه مش، تعادل بار، کش آمدن، مسیریابی اجتناب ناپذیر
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• A novel load balanced directory for distributed shared memory objects is proposed.
• It is suitable for dd-dimensional mesh-based topologies with nn nodes and d≥2d≥2.
• It attains O(d2logn) load approximation and O(dlogn) stretch approximation.
• Experimental results confirm the load balancing and low stretch benefits.
• Previous protocols only considered stretch and cannot control network load.

We present MultiBend, a novel distributed directory protocol for shared objects, suitable for large-scale distributed shared memory systems that use dd-dimensional mesh-based topologies, where d≥2d≥2. Each shared object has an owner node that can modify its value. The ownership may change by moving the object from one node to another in response to move requests. The value of an object can be read by other nodes with lookup requests. MultiBend balances the load of the network edges and nodes by forwarding each move or lookup request and response along a path consisting of multiple bends in the mesh. Using an oblivious routing protocol, the multi-bend paths have a small number of overlaps which helps to reduce the maximum edge and node utilization to achieve load balancing. At the same time, MultiBend achieves small stretch for the total path length of any sequence of move requests, compared to the total optimal path length. MultiBend guarantees O(d2logn)O(d2logn) approximation for the load, and O(dlogn)O(dlogn) approximation for the stretch due to move   requests, where nn is the number of nodes in the mesh network. It also guarantees O(d2)O(d2) approximation for the stretch of lookup requests. We evaluate MultiBend with simulations using various sequences of move and lookup   operations in a 16×1616×16 nodes 2-dimensional mesh network. We compare the simulation results to other protocols which are not tailored for load balancing and we find that our protocol is better by as much as the factor of 6.85 in terms of congestion in the worst-case. To the best of our knowledge, this is the first distributed shared memory directory protocol that considers the network load balancing aspect and achieves good approximation ratio for both the load and the stretch.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 78, April 2015, Pages 6–24
نویسندگان
, ,