Equivalence relations of synchronous schemes
Thesis (Ph.D.)--Memorial University of Newfoundland, 2000. Computer Science Bibliography: leaves 82-84 Synchronous systems are single purpose multiprocessor computing machines, which provide a realistic model of computation capturing the concepts of pipelining, parallelism and interconnection. The s...
Main Author: | |
---|---|
Other Authors: | |
Format: | Thesis |
Language: | English |
Published: |
2000
|
Subjects: | |
Online Access: | http://collections.mun.ca/cdm/ref/collection/theses3/id/90622 |
id |
ftmemorialunivdc:oai:collections.mun.ca:theses3/90622 |
---|---|
record_format |
openpolar |
institution |
Open Polar |
collection |
Memorial University of Newfoundland: Digital Archives Initiative (DAI) |
op_collection_id |
ftmemorialunivdc |
language |
English |
topic |
Systolic array circuits Iterative methods (Mathematics) |
spellingShingle |
Systolic array circuits Iterative methods (Mathematics) Cirovic, Branislav, 1964- Equivalence relations of synchronous schemes |
topic_facet |
Systolic array circuits Iterative methods (Mathematics) |
description |
Thesis (Ph.D.)--Memorial University of Newfoundland, 2000. Computer Science Bibliography: leaves 82-84 Synchronous systems are single purpose multiprocessor computing machines, which provide a realistic model of computation capturing the concepts of pipelining, parallelism and interconnection. The syntax of a synchronous system is specified by the synchronous scheme, which is in fact a directed, labelled, edge-weighted multi-graph. The vertices and their labels represent functional elements (the combinational logic) with some operation symbols associated with them, while the edges represent interconnections between functional elements. Each edge is weighted and the non- negative integer weight (register count) is the number of registers (clocked memory) placed along the interconnection between two functional elements. These notions allowed the introduction of transformations useful for the design and optimization of synchronous systems: retiming and slowdown. -- Two synchronous systems are strongly equivalent if they have the same stepwise behavior under all interpretations. Retiming a functional element in a synchronous system means shifting one layer of registers from one side of the functional element to the other. Retiming equivalence is obtained as the reflexive and transitive closure of this primitive retiming relation. Slowdown is defined as follows: for any system G = {V,E,w) and any positive integer c, the c-slow system cG = {V,E,w') is the one obtained by multiplying all the register counts in G by c. Slowdown equivalence is obtained as the symmetric and transitive closure of this primitive slowdown relation. Strong retiming equivalence is the join of two basic equivalence relations on synchronous systems, namely strong equivalence and retiming equivalence. Slowdown retiming equivalence is the join of retiming and slowdown equivalence. Strong slowdown retiming equivalence is the join of strong, slowdown and retiming equivalence. It is proved that both slowdown retiming and strong slowdown retiming equivalence of synchronous systems (schemes), are decidable. -- According to [Leiserson and Saxe, 1983a, 1983b], synchronous systems 5 and S' are equivalent if for every sufficiently old configuration c of 5, there exists a configuration d of S' such that when S started in configuration c and S' started in configuration c\ the two systems exhibit the same behavior. It is proved that two synchronous systems (schemes) are Leiserson equivalent if and only if they are strong retiming equivalent. -- The semantics of synchronous systems can be specified by algebraic structures called feedback theories. Synchronous schemes and feedback theories have been ax-iomatized equationally in [Bartha, 1987]. Here we extend the existing set of axioms in order to capture strong retiming equivalence. -- One of the fundamental features of synchronous systems is synchrony, that is, the computation of the network is synchronized by a global (basic) clock. Other, slower clocks can be defined in terms of boolean-valued flows. In order to describe the behavior of schemes with multiple regular clocks, we extend the existing algebra of schemes to include multiclocked schemes, and study the general idea of Leiserson equivalence in the framework of this algebra. |
author2 |
Memorial University of Newfoundland. Dept. of Computer Science |
format |
Thesis |
author |
Cirovic, Branislav, 1964- |
author_facet |
Cirovic, Branislav, 1964- |
author_sort |
Cirovic, Branislav, 1964- |
title |
Equivalence relations of synchronous schemes |
title_short |
Equivalence relations of synchronous schemes |
title_full |
Equivalence relations of synchronous schemes |
title_fullStr |
Equivalence relations of synchronous schemes |
title_full_unstemmed |
Equivalence relations of synchronous schemes |
title_sort |
equivalence relations of synchronous schemes |
publishDate |
2000 |
url |
http://collections.mun.ca/cdm/ref/collection/theses3/id/90622 |
genre |
Newfoundland studies University of Newfoundland |
genre_facet |
Newfoundland studies University of Newfoundland |
op_source |
Paper copy kept in the Centre for Newfoundland Studies, Memorial University Libraries |
op_relation |
Electronic Theses and Dissertations (9.43 MB) -- http://collections.mun.ca/PDFs/theses/Cirovic_Branislav.pdf a1477672 http://collections.mun.ca/cdm/ref/collection/theses3/id/90622 |
op_rights |
The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. |
_version_ |
1766113114474938368 |
spelling |
ftmemorialunivdc:oai:collections.mun.ca:theses3/90622 2023-05-15T17:23:32+02:00 Equivalence relations of synchronous schemes Cirovic, Branislav, 1964- Memorial University of Newfoundland. Dept. of Computer Science 2000 vi, 86 leaves Image/jpeg; Application/pdf http://collections.mun.ca/cdm/ref/collection/theses3/id/90622 eng eng Electronic Theses and Dissertations (9.43 MB) -- http://collections.mun.ca/PDFs/theses/Cirovic_Branislav.pdf a1477672 http://collections.mun.ca/cdm/ref/collection/theses3/id/90622 The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Paper copy kept in the Centre for Newfoundland Studies, Memorial University Libraries Systolic array circuits Iterative methods (Mathematics) Text Electronic thesis or dissertation 2000 ftmemorialunivdc 2015-08-06T19:18:45Z Thesis (Ph.D.)--Memorial University of Newfoundland, 2000. Computer Science Bibliography: leaves 82-84 Synchronous systems are single purpose multiprocessor computing machines, which provide a realistic model of computation capturing the concepts of pipelining, parallelism and interconnection. The syntax of a synchronous system is specified by the synchronous scheme, which is in fact a directed, labelled, edge-weighted multi-graph. The vertices and their labels represent functional elements (the combinational logic) with some operation symbols associated with them, while the edges represent interconnections between functional elements. Each edge is weighted and the non- negative integer weight (register count) is the number of registers (clocked memory) placed along the interconnection between two functional elements. These notions allowed the introduction of transformations useful for the design and optimization of synchronous systems: retiming and slowdown. -- Two synchronous systems are strongly equivalent if they have the same stepwise behavior under all interpretations. Retiming a functional element in a synchronous system means shifting one layer of registers from one side of the functional element to the other. Retiming equivalence is obtained as the reflexive and transitive closure of this primitive retiming relation. Slowdown is defined as follows: for any system G = {V,E,w) and any positive integer c, the c-slow system cG = {V,E,w') is the one obtained by multiplying all the register counts in G by c. Slowdown equivalence is obtained as the symmetric and transitive closure of this primitive slowdown relation. Strong retiming equivalence is the join of two basic equivalence relations on synchronous systems, namely strong equivalence and retiming equivalence. Slowdown retiming equivalence is the join of retiming and slowdown equivalence. Strong slowdown retiming equivalence is the join of strong, slowdown and retiming equivalence. It is proved that both slowdown retiming and strong slowdown retiming equivalence of synchronous systems (schemes), are decidable. -- According to [Leiserson and Saxe, 1983a, 1983b], synchronous systems 5 and S' are equivalent if for every sufficiently old configuration c of 5, there exists a configuration d of S' such that when S started in configuration c and S' started in configuration c\ the two systems exhibit the same behavior. It is proved that two synchronous systems (schemes) are Leiserson equivalent if and only if they are strong retiming equivalent. -- The semantics of synchronous systems can be specified by algebraic structures called feedback theories. Synchronous schemes and feedback theories have been ax-iomatized equationally in [Bartha, 1987]. Here we extend the existing set of axioms in order to capture strong retiming equivalence. -- One of the fundamental features of synchronous systems is synchrony, that is, the computation of the network is synchronized by a global (basic) clock. Other, slower clocks can be defined in terms of boolean-valued flows. In order to describe the behavior of schemes with multiple regular clocks, we extend the existing algebra of schemes to include multiclocked schemes, and study the general idea of Leiserson equivalence in the framework of this algebra. Thesis Newfoundland studies University of Newfoundland Memorial University of Newfoundland: Digital Archives Initiative (DAI) |