High level dataflow network partitioning using stochastic algorithms

A dataflow actor network is a method of representing a design, showing clearly how data moves from one actor to another in graph form, suitable to represent designs such as a video streaming application. The design representation is written in the CAL Actor Language and the intent is to eventually i...

Full description

Saved in:

Bibliographic Details
Main Author:	Woo, Yit Weng
Format:	Thesis
Language:	English
Published:	2018
Subjects:	TK Electrical engineering Electronics Nuclear engineering
Online Access:	http://eprints.utm.my/id/eprint/79583/1/WooYitWengMFKE2018.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.79583
record_format	uketd_dc
spelling	my-utm-ep.795832018-10-31T13:00:16Z High level dataflow network partitioning using stochastic algorithms 2018 Woo, Yit Weng TK Electrical engineering. Electronics Nuclear engineering A dataflow actor network is a method of representing a design, showing clearly how data moves from one actor to another in graph form, suitable to represent designs such as a video streaming application. The design representation is written in the CAL Actor Language and the intent is to eventually implement the design in hardware, more specifically, Field Programmable Gate Arrays (FPGA). Instead of using a large FPGA to fit the entire design, the design is seperated into smaller blocks to be implemented in multiple smaller FPGAs. This has multiple advantages such as savings in cost and time as well as allowing more flexibility according to the design need and available resources. The caveat of this design approach is that the connections between FPGAs would incur some latency and noise. As such, the actors in the design need to be partitioned accordingly to minimize these inter-FPGA connections. This project will be investigating two partitioning algorithms, namely the Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO) algorithms, to see which of these stochastic algorithms is better at partitioning the target design. Traditionally, partitioning is done using the cut cost as the optimized metric. While this would lead to less physical wires going across FPGAs, this could result in critical connections being compromised as it needs to traverse FPGAs. As such, this project will also investigate the feasibility of using communication rate as the partitioning criterion to better ensure that the connections between FPGAs are not critical such that the penalty can be tolerated. This project will use the profiles of a basic FIR Digital Filter as well as larger HEVC Decoder and MPEG-4 AVC Decoder test cases. The partitioning algorithms will be written in Java, using information regarding the actors and connections that are in the profile of each design. The results are analyzed to determine which algorithm is more suited to separate the design into balanced partitions as well as whether communication rate is a better partitioning criterion than cut cost for certain applications. The results obtained will also be compared with results obtained using the deteministic Fiduccia-Mattheyses (FM) algorithm. 2018 Thesis http://eprints.utm.my/id/eprint/79583/ http://eprints.utm.my/id/eprint/79583/1/WooYitWengMFKE2018.pdf application/pdf en public masters Universiti Teknologi Malaysia, Faculty of Electrical Engineering Faculty of Electrical Engineering
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	TK Electrical engineering Electronics Nuclear engineering
spellingShingle	TK Electrical engineering Electronics Nuclear engineering Woo, Yit Weng High level dataflow network partitioning using stochastic algorithms
description	A dataflow actor network is a method of representing a design, showing clearly how data moves from one actor to another in graph form, suitable to represent designs such as a video streaming application. The design representation is written in the CAL Actor Language and the intent is to eventually implement the design in hardware, more specifically, Field Programmable Gate Arrays (FPGA). Instead of using a large FPGA to fit the entire design, the design is seperated into smaller blocks to be implemented in multiple smaller FPGAs. This has multiple advantages such as savings in cost and time as well as allowing more flexibility according to the design need and available resources. The caveat of this design approach is that the connections between FPGAs would incur some latency and noise. As such, the actors in the design need to be partitioned accordingly to minimize these inter-FPGA connections. This project will be investigating two partitioning algorithms, namely the Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO) algorithms, to see which of these stochastic algorithms is better at partitioning the target design. Traditionally, partitioning is done using the cut cost as the optimized metric. While this would lead to less physical wires going across FPGAs, this could result in critical connections being compromised as it needs to traverse FPGAs. As such, this project will also investigate the feasibility of using communication rate as the partitioning criterion to better ensure that the connections between FPGAs are not critical such that the penalty can be tolerated. This project will use the profiles of a basic FIR Digital Filter as well as larger HEVC Decoder and MPEG-4 AVC Decoder test cases. The partitioning algorithms will be written in Java, using information regarding the actors and connections that are in the profile of each design. The results are analyzed to determine which algorithm is more suited to separate the design into balanced partitions as well as whether communication rate is a better partitioning criterion than cut cost for certain applications. The results obtained will also be compared with results obtained using the deteministic Fiduccia-Mattheyses (FM) algorithm.
format	Thesis
qualification_level	Master's degree
author	Woo, Yit Weng
author_facet	Woo, Yit Weng
author_sort	Woo, Yit Weng
title	High level dataflow network partitioning using stochastic algorithms
title_short	High level dataflow network partitioning using stochastic algorithms
title_full	High level dataflow network partitioning using stochastic algorithms
title_fullStr	High level dataflow network partitioning using stochastic algorithms
title_full_unstemmed	High level dataflow network partitioning using stochastic algorithms
title_sort	high level dataflow network partitioning using stochastic algorithms
granting_institution	Universiti Teknologi Malaysia, Faculty of Electrical Engineering
granting_department	Faculty of Electrical Engineering
publishDate	2018
url	http://eprints.utm.my/id/eprint/79583/1/WooYitWengMFKE2018.pdf
_version_	1747818261869756416

High level dataflow network partitioning using stochastic algorithms

Similar Items