# Presentation: 154998

## Machine Learning and Grid Optimization

- Noah Edelson
- Distributed Systems Department

## Motivation

- Computation is important to science.
- Search is one of the most important problems in computation.
- Uninformed “blind” search is the most general search technique.
- Uninformed searches often perform better than uninformed programmers.

## The Black Art of Fussing with Parameters

- > Rather than cranking the buffers all the way up, it may be better to
- > use multiple streams to fill the pipe.  It may not possible to saturate
- > a a fat pipe with just one connection for the above reasons, but also
- > because of traffic shapers and various other limits.  You can always
- > try of course :-)  For parallel connections use some reasonable
- > estimate, e.g. divide the maximum "pipe width" (bandwith * rtt) by what
- > you seem to be able to get out from a single stream, give or take a few
- > more streams.  It would probably help to be multi-threaded if using
- > multiple streams (to avoid txqueuelen exhaustion).  Alternatively,
- > simply copying several files in parallel achieves the same.

## Blind Search

- Queue <- MakeQueue(Initial-State)
-  while( Not Empty(Queue) ){
-       Node <- Remove-Front(Queue)
-       if( Goal-Test(Node) )
-              return Solution
-     Queue <- Queuing-FN( Expand(Node), Queue)
- }
- return Failure

## Search Taxonomy

## Evolutionary Computation

- .

- Recombination
-  (crossover)

- Mutation

- Selection

- Replacement

- Borrowed from Alba & Troya - Improving flexibility and efficiency by adding parallelism to genetic algorithms, **Statistics and Computing 12**

## Genetic Algorithms

*t*

*t + 1*

***reproduction***

***selection***

- Borrowed from Alba & Troya - Improving flexibility and efficiency by adding parallelism to genetic algorithms, **Statistics and Computing 12**

## “Combinatorial Explosion”

- A search, by definition, picks 1 of N solutions from the solution space.
- Given a bitstring with cardinality |N|, there are 2^|N| possible states to search.
- A well known AI professor at Cal claims that GA ignore the “combinatoral explosion” of the search space.  He is wrong.

## The Black Art of Fitness Functions

_**A “good” fitness function converges quickly.**_
- Minimize |genes| (degrees of freedom)
- Avoid “Deceptive Trap Functions”
- Encourage “smooth” fitness functions
- Decouple fitness dependence between genes
- -- What happens when your fitness function halts?

## A Solution to the Entscheidungsproblem!!!

- When all else fails- **give up**!
- A solution whose evaluation halts is decidedly unfit.
- Boils down to “throwing out the outliers”

## Parameter Tuning by way of Search (2 steps!)

- An optimizer simply performs a “search for optimal performance.”
- Step 1) Encode your input parameters
- Step 2) Invent a fitness metric-
- 		I used **ExecutionTime^-1**

## Example Fitness Function

- 	def testFunc(data, args=''):
- 	    if not data: return 3, 1.0, 0.0
-    p,b,t     = int(1+data[0]*10.0) , \
- 	                    8*1024+int(int(data[1]*255.0))*1024, \
- 	                    8*1024+int(int(data[2]*255.0)*1024)
- 	startTime = time.time()
- 	    for samples in range(num_samples):
- 	       lazy_forker(‘globus-url-copy’ + ' -p ' + str(p)' -bs ' +str(b) + ' -tcp-bs’\
-    	+ str(t) + ' ' + src + ' ' + dst, threshHold)
- 	endTime   = time.time() - startTime
- 	return 1.0/endTime

## Step 3?

- Step 3) Grin in satisfaction, as your GA will explore multiple dimensions of your solution-space at once.

## Results

-     Globus-url-copy	pyGlobus-url-copy
- 		(2x avg)		(4x avg)
- 		_**Performance Boost**_
- 64	    35%		19%
- 128	    22			15
- 192	    08			00
- 256	    03			06
_**mb**_

## Results

- Globus-url-copy and pyGlobus-url-copy are similar in terms of performance given input parameters and running environment.
- Parameter tuning affords both utilities a noticeable increase in performance given little knowledge of the problem domain.

## Why an optimizer service?

- .

**Optimizer**
-  *TuneService(FF)		   *TestEnv
-  *Save/Load Tunings[Env]

**GridServiceA**(x,y,z)

- FitnessFunction(x,y,z)

- FitnessFunction(x,y,z)

**GridServiceB**(w,q,r)

## Too Much Work?

- Writing an application-tuning fitness function is similar to wrapping or service-ifying the application.
-  If you wrap a well-used app whose performance is sensitive to the parameters you support, you might as well provide a mechanism for tuning those parameters for higher performance.

## Future Work

- Service-ify the GA
- 	- What standard to use?
- Production runs on WAN?
- 	- PlanetLab, EMULab?
- What besides pyGlobus-url-copy and globus-url-copy?
- 	- Grid Schedulers?
- 	- RLS Strategies?
- 	- Parameter tuning for important applications & services?

## Thanks!

- 			Have a good weekend!