Formal Description of Systolic Algorithms and an Analysis of the Information Flow.
Saved in:
| Title: | Formal Description of Systolic Algorithms and an Analysis of the Information Flow. |
|---|---|
| Authors: | Aso, Hirotome1, Yasuyoshi Inagaki2 |
| Source: | Systems & Computers in Japan. Jun88, Vol. 19 Issue 6, p14-24. 11p. |
| Subjects: | Systolic array circuits, Integrated circuits, Hardware, Algorithms, Mathematical functions, Electronic data processing |
| Abstract: | Due to the development of VSLI fabrication technologies systolic algorithms are now being implemented as practical hardware. As a result, it is becoming more important to know their design methodologies and the scope of their object problems. In this paper as a basis to know the scope of the object problems we formalize systolic algorithms as mathematical objects in a strict manner. In other words, it is formalized by a triple systolic array, a data location space and a set of timing functions. Moreover, equivalence between systolic arrays is defined. Under this formulation we define a data dependency graph as a tool for analyzing the flow of information, and show that wiring structures can be classified into several types. We give a condition that it is reduced equivalently to a simple memory-type one. Finally, we consider the data flow processed in a systolic array and give not only an equation for data flow, but also the initial arrangement for a necessary encounter for interaction between data flows. [ABSTRACT FROM AUTHOR] |
| Copyright of Systems & Computers in Japan is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 13997902 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Formal Description of Systolic Algorithms and an Analysis of the Information Flow. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Aso%2C+Hirotome%22">Aso, Hirotome</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Yasuyoshi+Inagaki%22">Yasuyoshi Inagaki</searchLink><relatesTo>2</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Systems+%26+Computers+in+Japan%22">Systems & Computers in Japan</searchLink>. Jun88, Vol. 19 Issue 6, p14-24. 11p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Systolic+array+circuits%22">Systolic array circuits</searchLink><br /><searchLink fieldCode="DE" term="%22Integrated+circuits%22">Integrated circuits</searchLink><br /><searchLink fieldCode="DE" term="%22Hardware%22">Hardware</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+functions%22">Mathematical functions</searchLink><br /><searchLink fieldCode="DE" term="%22Electronic+data+processing%22">Electronic data processing</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Due to the development of VSLI fabrication technologies systolic algorithms are now being implemented as practical hardware. As a result, it is becoming more important to know their design methodologies and the scope of their object problems. In this paper as a basis to know the scope of the object problems we formalize systolic algorithms as mathematical objects in a strict manner. In other words, it is formalized by a triple systolic array, a data location space and a set of timing functions. Moreover, equivalence between systolic arrays is defined. Under this formulation we define a data dependency graph as a tool for analyzing the flow of information, and show that wiring structures can be classified into several types. We give a condition that it is reduced equivalently to a simple memory-type one. Finally, we consider the data flow processed in a systolic array and give not only an equation for data flow, but also the initial arrangement for a necessary encounter for interaction between data flows. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Systems & Computers in Japan is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=13997902 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1002/scj.4690190602 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 11 StartPage: 14 Subjects: – SubjectFull: Systolic array circuits Type: general – SubjectFull: Integrated circuits Type: general – SubjectFull: Hardware Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Mathematical functions Type: general – SubjectFull: Electronic data processing Type: general Titles: – TitleFull: Formal Description of Systolic Algorithms and an Analysis of the Information Flow. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Aso, Hirotome – PersonEntity: Name: NameFull: Yasuyoshi Inagaki IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 06 Text: Jun88 Type: published Y: 1988 Identifiers: – Type: issn-print Value: 08821666 Numbering: – Type: volume Value: 19 – Type: issue Value: 6 Titles: – TitleFull: Systems & Computers in Japan Type: main |
| ResultId | 1 |
