Award Date

12-1-2013

Degree Type

Thesis

Degree Name

Master of Science in Electrical Engineering (MSEE)

Department

Electrical and Computer Engineering

First Committee Member

Henry Selvaraj

Second Committee Member

Emma Regentova

Third Committee Member

Shahram Latifi

Fourth Committee Member

Laxmi Gewali

Fifth Committee Member

Kathryn H. Korgan

Number of Pages

105

Abstract

Topic of this master's thesis is connected with task allocation algorithms and mesh networks. Author of this work has already graduated from Wroclaw, University of Technology (Poland) where during his studies he created software simulation environment for two different task allocation algorithms for mesh networks:Adaptive ScanandFrame Sliding. Those algorithms were compared by two, main parame- ters: simulation time and average mesh fulfillment (utilization level). All simulations were done in software environment which was developed specially for that research. This application was based on few, different types of objects: task (width, height, processing time), task queue (different number of tasks), task allocator (where different allocation strategies were implemented) and mesh structure (width, height). Whole environment was implemented using C++ language and Xcode IDE (no GUI - simulator is only a tool for this specific research, not a final product).

This work is based on three very well known task allocation algorithms:First Fit,Frame SlidingandAdaptive Scanand also one new approach (author's own idea based on the Adaptive Scan approach) -Snail Algorithm. If new algorithm is able to scan mesh network more accurately, then tasks from the queue are allocated faster than for other algorithms (time needed for processing whole queue will be shorter). If there are more tasks on the mesh at the same time, then overall mesh utilization level (mesh fulfillment) is higher.

It was assumed that all the nodes were exactly the same and there was no delay between them so the communication was instant. This simulator is not taking into account a lot of different parameters and delays which are however present in real life situations. For example communications delays, time needed for allocator to allocate tasks from queue on the mesh structure etc. All the experiments are based only on the execution time inside the mesh so it was easier to compare all algorithms and conclude which task arrangement is providing shorter task queue execution time and better mesh utilization level.

Keywords

Adaptivescan; Algorithms; Allocation; Computer networks; Firstfit; Framesliding; Mesh; Snail

Disciplines

Computer Engineering | Electrical and Computer Engineering

Language

English


Share

COinS