Find results with:

Add another field

Search by date

to

Searching collections:

Dartmouth Dissertations

Add or remove collections

Home Dartmouth Dissertations Page 1

Reference URL

To link to the entire object, paste this link in email, IM or document

To embed the entire object, paste this HTML in website

To link to this page, paste this link in email, IM or document

To embed this page, paste this HTML in website

An effective distributed caching strategy for partial result reuse for discrete optimization problems.

you wish to report:

Your comment:

Your Name:

Submit

Cancel

...

Back to top

Powered by CONTENTdm®

Call No.	Ph.D. 2009
Author	Kim, Keum Joo.
Title	An effective distributed caching strategy for partial result reuse for discrete optimization problems.
Date	2009
Abstract	Evolutionary Computation (EC) is one of the most advanced computational techniques. It has been frequently and successfully used to find good solutions to many complicated optimization problems with limited computational resources. EC is the iterative procedure of examining a set of possible solutions (called the population) and modifying the solutions based on a method relying on probability and randomization. As a result, the quality of the final solution achieved depends on the number of solutions investigated during the evolutionary procedure in general. Although this procedure is essential to find good solutions efficiently, its computational load is a well known bottleneck of EC. In particular, for optimization problems whose objective function is highly complicated, population-based approaches may not be applicable and technical advancement to save computing time is necessary. Previously, several methods were studied to address this issue such as reusing partial fitness computations, approximating fitness function and hybridizing local and global searches. Parallel and distributed computation has been studied as well to enhance performance by increasing computational resources. In particular, caching, which reuses partial values of objective (fitness) function computations, is one of the most promising techniques, because it maintains the accuracy of the original objective function, as opposed to approximation, and is easily compatible with other performance enhancement techniques. Previously, an effective caching strategy was developed to save overall computational time of single processor EC in solving a challenging Hydrophobic-Polar protein folding problem. Although employing this caching strategy saves a significant amount of time, performance is limited when the local population becomes very diverse. Since the performance of caching relies on the amount of redundant computation, highly redundant computation improves caching performance but hinders the exploratory capability of EC. In order to find good solutions with limited resources we need to cope with appropriate diversity. Thus, local caches should be diversified accordingly to enhance the overall performance of EC. To achieve this, we developed a caching migration using communication among neighboring processors as a means to diversify local caches. These local caches are diversified by migrating parts of them among neighboring processors, whereas previous caching strategy relied only on locally computed results. In caching migration, communication messages are composed of partial values of the objective function and their relations. Our contribution in this thesis is the development of a theoretical model of parallel and distributed EC embedded with a distributed caching strategy and also to investigate its effectiveness in solving complex discrete optimization problems. From the theoretical and empirical study we have conducted so far, we conclude that our distributed caching strategy is a promising technique to enhance the time performance of parallel and distributed EC. This will broaden the applicability of EC as performance is improved by the migration of local caches in addition to the use of locally redundant computations through an effectively designed caching strategy.
Description	xi, 143 leaves : ill. (some col.) 28 cm.
Format	application/pdf
Advisor	Santos, Eugene, Jr., Cybenko, Georege, Shepherd, Simon G., Santos, Eunice E.
Subject	Evolutionary computation. Cache memory. Mathematical optimization. Protein folding -- Computer simulation.
College	Thayer School of Engineering.
Issuing Body	Dartmouth Dissertations are made available through the Dartmouth Digital Library.
Degree	Thesis (Ph.D.)--Dartmouth College.
Copyright	All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means without permission in writing from the author.
DOI	http://dx.doi.org/10.1349/ddlp.261

Title	Page 1
Format	application/pdf
Issuing Body	Dartmouth Dissertations are made available through the Dartmouth Digital Library.
Degree	Thesis (Ph.D.)--Dartmouth College.
Full Text	AN EFFECTIVE DISTRIBUTED CACHING STRATEGY FOR PARTIAL RESULT REUSE FOR DISCRETE OPTIMIZATION PROBLEMS A Thesis Submitted to the Faculty in partial fulfillment of the requirements for the degree of Doctor of Philosophy by Keum Joo Kim Thayer School of Engineering Dartmouth College Hanover, New Hampshire June 2009 Examining Committee Chairman Eugene Santos Jr. Member E George Cybenko Member E Simon G. Shepherd Member E Eunice E. Santos ____________________ Brian W. Pogue Dean of Graduate Studies ____________________

Find results with:

Searching collections:

Home Dartmouth Dissertations Page 1

An effective distributed caching strategy for partial result reuse for discrete optimization problems.

Object Description

Description

An effective distributed caching strategy for partial...

An effective distributed caching strategy for partial...

	All
	Pages Enter page numbers or page ranges separated by commas. For example: 1,3,5-12