ProximityScheduler - Revision history

Ryan Lane: Text replace - "NOTOC" to ""

2013-02-17T23:30:30Z

Text replace - "__NOTOC__" to ""

Clark Boylan at 21:22, 16 February 2013

2013-02-16T21:22:09Z

Jsuh at 12:50, 10 September 2012

2012-09-10T12:50:15Z

Jsuh at 12:51, 29 August 2012

2012-08-29T12:51:18Z

New page

__NOTOC__
= Proximity Scheduler =

== Why proximity scheduler ==

In heterogeneous high performance computing environment on [[OpenStack]], proximity of hosts is critical to achieve high performance due to the cost of communication among the hosts. Thus, the scheduler needs to be able to use topology and location information of each host to allocate a set of hosts that are located close each other.

== Approach ==

Scheduler gets topology and location information at the time of deployment or at the time of system upgrade. When more than one instance is requested and proximity requirement is set, the scheduler allocates a set of hosts that are close each other. It involves modification of filter_scheduler to be able to consider available hosts at the same time and returns the best chosen hosts instead of returning one by one. Cost function also needs modification to consider the topology and location of each host to choose the best set of hosts.

Many different algorithms can be employed to choose the best set. For a large system, exhaustive search is not feasible, so a heuristic algorithm needs to be employed. One possible algorithm is using breadth-first search with modifications of considering more than one level when choosing next candidates. The algorithm can run N times with each different node as the first candidate host, where N is the number of available hosts. From the candidate hosts, a host that has least distance from already-chosen set of hosts is added to the chosen set.

The following algorithm illustrate it, but ntoe that it is not very accurate.

<pre><nowiki>
for each host h in available hosts:
chosen_set(h) = h
dist = 2
while True:
candidate_set = hosts that are not farther than dist from h
while candidate_set is not empty:
choose a host that has least distance from all of hosts in chosen_set
add the chosen host to chosen_set; remove it from candidate_set
if chose_set has the required number of host
break
dist++
choose the best chosen_set(h)
</nowiki></pre>

← Older revision		Revision as of 23:30, 17 February 2013
Line 1:		Line 1:
−	~~__NOTOC__~~	+
	= Proximity Scheduler =		= Proximity Scheduler =

← Older revision		Revision as of 12:50, 10 September 2012
Line 29:		Line 29:
	choose the best chosen_set(h)		choose the best chosen_set(h)
	</nowiki></pre>		</nowiki></pre>
		+
		+
		+	== Files to be modified ==
		+
		+	=== nova/scheduler/filter_scheduler.py ===
		+
		+	Curent filter_scheduler chooses hosts one by one in greedy algorithm. This does not work for proximity scheduler that needs to get a set of hosts that are close each other. Thus, instead of getting hosts one by one, it needs to be modified a set of hosts at once.
		+
		+	=== nova/scheduler/least_cost.py ===
		+
		+	Least cost file needs modification to have the new host selection algorithm.

@@ Line 13: / Line 13: @@
 The following algorithm illustrate it, but ntoe that it is not very accurate.
 <pre><nowiki>
@@ Line 29: / Line 28: @@
 choose the best chosen_set(h)
 </nowiki></pre>
 == Files to be modified ==

ProximityScheduler - Revision history

Ryan Lane: Text replace - "__NOTOC__" to ""

Clark Boylan at 21:22, 16 February 2013

Jsuh at 12:50, 10 September 2012

Jsuh at 12:51, 29 August 2012

Ryan Lane: Text replace - "NOTOC" to ""