Optimizing Task Assignment and Job Scheduling in Distributed Systems

Scheduling is important in handling big data and high-performance computing. In this setup, jobs run on many servers. Each job usually consists of many tasks that need access to specific data pieces, which may be stored on different servers. Knowing where the data is stored helps assign tasks to the right servers, which is crucial for Efficiency. This paper looks at how to best assign tasks to servers, especially when jobs come in one after another.

#Problem Overview

When jobs arrive online, they each consist of several independent tasks. Each task needs a specific data piece to work on, and these data pieces are stored in chunks across different servers. The aim is to minimize the time it takes to complete all tasks in each job, from when the job arrives until all tasks are finished.

The scheduling problem has two main parts: assigning tasks to servers and deciding the order in which tasks are completed. Assigning tasks involves deciding which tasks go to which servers, while job reordering involves deciding the sequence in which tasks will be executed.

#Task Assignment

Task assignment can be imagined like connecting two groups: tasks and servers. Tasks that can be processed together can be grouped based on the servers that have the needed data. The goal here is to ensure that tasks are assigned in a way that leads to speedier job completion.

#Job Reordering

Job reordering focuses on adjusting the order in which tasks are processed. By changing the order of task execution, we can also improve overall completion times. This becomes critical when there are multiple tasks waiting to be executed.

#Previous Work

Past studies have looked at task assignment and job scheduling separately or together. Some methods have focused on scheduling based on estimated completion times, while others have explored fairness in resource distribution. However, not all have considered the situation where data is stored on multiple servers, which simplifies the problem too much.

Some studies have examined task assignment in a network flow context, where task allocation is treated like solving a maximum flow problem. Other approaches have not provided a deep performance analysis of their methods.

#Our Approach

Our work mainly deals with assigning tasks while keeping data locality in mind. This is done in real-time as jobs arrive. We want to minimize the time it takes to finish tasks in a job, especially when we have no prior knowledge of future jobs.

#Scenarios

We consider two scenarios in our analysis:

1. The first is when tasks are processed in a first-come-first-served manner. Here, the focus is on balancing out the server busy times as much as possible.
2. The second scenario allows for prioritizing and reordering tasks, which can further speed up job completion.

#Task Assignment as a Problem

We model the task assignment challenge as a mathematical problem. We create a graph with two sets of nodes: one for tasks and another for servers. Our aim is to connect the tasks to the right servers efficiently while keeping in mind how busy each server is before the new job arrives.

To determine how to assign tasks, we consider how long it would take to process all tasks and then find ways to balance this load across servers.

#Developing Algorithms

We introduce new algorithms to tackle this problem.

1. Optimal Balanced Task Assignment (OBTA) - This algorithm efficiently narrows down potential solutions to find the best way to assign tasks.

2. Water-Filling Algorithm (WF) - This is an approximate method that allocates tasks to servers one group at a time. It aims to keep the busy times of the servers balanced.

3. Replica-Deletion (RD) - This heuristic removes unnecessary task replicas from servers to keep the load balanced while still assigning tasks effectively.

#Job Reordering Algorithms

We also look into an extended version of our algorithms that allows for job reordering. This method uses a strategy similar to prioritizing tasks based on how soon they can be completed. When a new job comes in, we estimate the time left to finish ongoing jobs and reorder them accordingly. This method helps minimize average completion times even further.

#Experimental Setup

To test our algorithms, we used real data from a job trace dataset. This data included many jobs and tasks, allowing us to observe how different algorithms performed under various conditions.

#Metrics for Success

We measured the performance of our algorithms based on two main factors:

• Average job completion time, which indicates how fast jobs are finished.
• Computational Overhead, which shows how much processing power and time is required by each algorithm.

#Simulation Results

We performed simulations to compare how well our algorithms functioned under various system loads. Here are some key findings:

• Efficiency Gains: The OBTA algorithm showed significant efficiency improvements over traditional methods.

• Performance of WF: The WF algorithm was nearly as effective as OBTA but operated with much lower overhead, making it practical for larger workloads.

• Comparing RD: The RD algorithm often beat the performance of WF but required more computational resources, which aligns with our expectations.

• Job Reordering Benefits: The job reordering algorithms showed resilience against uneven data distributions. They managed to maintain lower job completion times even when the availability of data was skewed.

• Speed of OCWF-ACC: This version of the algorithm significantly improved upon its predecessor by reducing the amount of time and resources needed to compute job orders.

#Impacts of Server Counts and Capacities

Through simulations, we found that having more available servers tends to reduce job completion times. This is because more servers allow tasks to be distributed better, leading to a more balanced workload. Similarly, increasing server processing capacity also resulted in shorter job completion times.

#Related Work in Scheduling

Job scheduling has been a focus in various fields, addressing both theoretical and practical aspects. Many algorithms have been developed that aim to balance efficiency, fairness, and resource allocation depending on the situation.

Several papers have discussed related topics, such as optimizing resource allocation in distributed job execution settings. Others have looked at how to achieve fairness and minimize unnecessary data movement during processing.

#Conclusion

In our study, we examined the challenge of task assignment and job scheduling in distributed computing systems. We formulated this problem mathematically and developed several algorithms to improve efficiency and performance. Using real-world data traces, we validated our methods and demonstrated significant improvements in minimizing job completion times while keeping computational overhead low. The findings show that both task assignment and the ability to reorder jobs play crucial roles in optimizing performance in distributed environments.

Future work may involve adapting these algorithms to fit different computing scenarios and enhance their flexibility within ever-changing job execution dynamics.