miun.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Memory modeling and synthesis for real-time video processing systems
Mid Sweden University, Faculty of Science, Technology and Media, Department of Information Technology and Media. (Electronics Design Division, STC)
Responsible organisation
2006 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis, a new design methodology and new tools for modeling and synthesis of real-time video processing systems are presented. A real-time video processing system is a system that performs computations on a continuous sequence of images. Image processing is a memory intensive application. This, in turn, leads to the design challenge of bridging the classical gap of speed between memories and computational units. Several techniques exist for building memory hierarchies that exploit data- locality and reuse in order to overcome this memory gap. However, the support from tools to aid the designer in dataflow analysis and memory design is very modest. Additional constructs for modeling electronic systems enable well-known sequential programming languages such as C/C++ to be used for system modeling. Ocapi and SystemC, two object-oriented specification methods are compared in a case study. In this study, SystemC is found to be the most suitable specification method for video processing systems. Most operations invoked in video processing are neighborhood oriented. For a video system designer, this spatio-temporal collection of pixels represents a natural abstraction. In addition, the same pixel neighborhood reflects data dependencies that are crucial to system synthesis. An extended SystemC modeling methodology, called IMEM is presented. IMEM can be used to capture memory transactions and stream interfaces based on the pixel neighborhood as an abstraction. Two important steps towards synthesis of video systems onto Field Programmable Gate Arrays (FPGAs) are presented. These two steps are parts of a decomposition of the complete synthesis task. Firstly, the optimal sizes and placements of all FIFO-buffers in the memory system are optimized. Bit-widths, pipelining and possible sharing of FIFO-buffers among several data flow dependencies are considered at this step. Secondly, the set of FIFO-buffers are allocated onto a set of dual-ported fined grained memories. Both synthesis steps are formally modeled using network flow techniques and linear programming. In addition, a synthesis method that can automatically transform an IMEM model of a single spatial neighborhood into a multimedia processor implementation is presented. The cache and the instruction scheduler performance are both optimized by the tool. IMEM is an application specific methodology that provides the nonhardware skilled video designer with an easy programming model and an FPGA synthesis tool. Memory usage is modeled separately from computation. This is a key feature since memory usage is accepted as being the biggest design bottleneck for video processing.

Abstract [sv]

I denna avhandling presenteras en ny metod och nya verktyg för modellering och syntes av videobearbetande system i realtid. Ett videobearbetande system är ett system som utför beräkningar på en kontinuerlig ström av bilder. Bildbehandling är en minnesintensiv applikation. Detta i sin tur leder till en stor utmaning för konstruktören, nämligen att överbrygga en välkänd skillnad i hastighet mellan minnen och beräkningsenheter. Det finns ett flertal välkända tekniker att övervinna denna skillnad genom att utnyttja lokaliteten och återanvändningen av data. Stöd från befintliga verktyg som kan hjälpa konstruktören med dataflödesanalys och minneskonstruktion kan dock anses vara blygsam. Genom att tillföra mekanismer för modellering av elektroniska system, så kan traditionella sekventiella programmeringsspråk, så som C/C++ användas för modellering av system. Ocapi och SystemC är två objektorienterade specifikationsmetoder som jämförts i en fallstudie. I denna studie framstår SystemC som bäst lämpad för specifikation av videobearbetande system. De flesta bildbehandlingsoperationer arbetar på en lokal mängd av bildpunkter. För en bildbehandlingskonstruktör så framstår denna lokala mängd av bildpunkter som en abstraktion. Tillika representerar samma mängd bildpunkter de databeroenden som är avgörande vid syntes. I denna avhandling presenteras IMEM, en ny specifikationsmetod som kan användas till att modellera minnesanvänding och transaktioner genom att utnyttja en lokal mängd bildpunkter. Två betydelsefulla steg mot att med automatik kunna översätta en modell i IMEM till en implementation i en Field Programmable Gate Array (FPGA) beskrivs. Dessa två problemformuleringar är delsteg i hela syntesprocessen. I första steget optimeras placering och storlek av alla buffertminnen. Hänsyn tas härvid till bitbredd, pipelining och eventuell delning av buffertar mellan flera databeroenden. I det andra steget allokeras buffertminnen till en mängd små dubbelportade minnen. Båda syntesstegen modelleras formellt med hjälp av nätverksflöden och linjär programmering. Dessutom presenteras en syntesmetod som kan översätta en enkel IMEMmodell till en implementation i en mediaprocessor. Cache-minneshantering och schemaläggning av instruktioner optimeras av verktyget. IMEM är en applikationsspecifik metod för videosystem som tillhandahåller en enkel programmeringsmodell och ett syntesverktyg för FPGA-kretsar. Minnesanvändning modelleras separat från beräkningar. Detta är en viktig egenskap, eftersom i huvudsak minnestransaktionerna kommer att begränsa systemets prestanda.

Place, publisher, year, edition, pages
Sundsvall: Mittuniversitetet , 2006. , 107 p.
Series
Mid Sweden University doctoral thesis, ISSN 1652-893X ; 8
Keyword [en]
memory modeling
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:miun:diva-5883Local ID: 4090ISBN: 91-85317-19-5 (print)OAI: oai:DiVA.org:miun-5883DiVA: diva2:30916
Public defence
2006-05-18, O102, Sundsvall, 13:15 (English)
Opponent
Supervisors
Available from: 2008-09-30 Created: 2009-05-06 Last updated: 2011-02-06Bibliographically approved
List of papers
1. Analysis of modeling and simulation capabilities in systemC and Ocapi using a video filter design
Open this publication in new window or tab >>Analysis of modeling and simulation capabilities in systemC and Ocapi using a video filter design
2002 (English)In: System on chip design languages :: extended papers : best of FDL’01 and HDLCon’01, Boston, Mass: Kluwer Academic Publishers, 2002, 283- p.Chapter in book (Other academic)
Abstract [en]

Several system specification languages are emerging from C and C++. This development is driven by the large competence that exists for these languages. The programming language itself lacks many of the necessary constructs one requires from a specification language. Therefore, specification languages based on C/C++ are often a superset of the programming language. Where all the necessary constructs for system specification is added to the language. This paper evaluates and compares SystemC and Ocapi, which both are specification methods based on C++. The analysis is done as a case study with focus on the modelling and simulation effectiveness for video systems. The system we have selected is a spatio-temporal video filter. This video filter is characterised by high computational complexity, by high requirements on memory size and memory bandwidth.

Place, publisher, year, edition, pages
Boston, Mass: Kluwer Academic Publishers, 2002
Series
The ChDL series
Keyword
SystemC, comparison, system design, video systems
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-5542 (URN)589 (Local ID)1-40207046-2 (ISBN)589 (Archive number)589 (OAI)
Available from: 2008-12-16 Created: 2008-12-16 Last updated: 2012-01-18Bibliographically approved
2. IMEM: An Object Oriented Memory- and Interface Modeling Approach for Real-Time Video Processing Systems
Open this publication in new window or tab >>IMEM: An Object Oriented Memory- and Interface Modeling Approach for Real-Time Video Processing Systems
2002 (English)In: Proceedings / FDL '02, Forum on Specification & Design Languages, Marseille, France, Sept 24-27, 2002: FDL ; 5 (Marseille) : 2002.09.24-27, Marseille, 2002Conference paper, (Refereed)
Place, publisher, year, edition, pages
Marseille: , 2002
Keyword
IMEM Object Oriented Memory- and Interface Modeling
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-1657 (URN)279 (Local ID)279 (Archive number)279 (OAI)
Available from: 2008-09-30 Created: 2008-09-30 Last updated: 2011-04-08Bibliographically approved
3. Conceptual Interface and Memory-Modelling for Real-Time Image Processing Systems- IMEM: A tool for Modeling, Simulation and Design Parameter Extraction
Open this publication in new window or tab >>Conceptual Interface and Memory-Modelling for Real-Time Image Processing Systems- IMEM: A tool for Modeling, Simulation and Design Parameter Extraction
2002 (English)In: Proceedings of 2002 IEEE Workshop on Multimedia Signal Processing, MMSP 2002: 9-11 Dec. 2002 , St.Thomas, VI, USA, IEEE conference proceedings, 2002, 138-141 p., 1203267Conference paper, (Refereed)
Abstract [en]

Most operations invoked in video processing systems are neighborhood oriented. For a video system designer, this limited spatio-temporal collection of pixels represents a natural abstraction. In this paper, we present a basic set of object-oriented design entities. Entities, which can be combined to capture an interface and memory model at a conceptual level, with the neighborhood as an abstraction. These design entities, called IMEM, are implemented as an extension to SystemC. IMEM supports conceptual modeling that excludes implementation details and has explicit data dependency built-in to the model. This makes IMEM a very efficient starting point for design-space exploration and system synthesis. We propose two workflows. The first is a system development workflow, where IMEM represents the starting point of a gradual refinement process, supported by an automated design space exploration step. The second workflow, based on direct mapping of the interface and memory model is presented as being suitable for rapid prototyping. A spatio-temporal noise-reduction filter is selected as a test-vehicle in order to demonstrate the feasibility of IMEM.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2002
Keyword
Conceptual Interface, Memory-Modelling Image Processing
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-1656 (URN)10.1109/MMSP.2002.1203267 (DOI)2-s2.0-33947602480 (Scopus ID)278 (Local ID)0780377133 (ISBN)278 (Archive number)278 (OAI)
Conference
2002 5th IEEE Workshop on Multimedia Signal Processing, MMSP 2002; St. Thomas; United States; 9 December 2002 through 11 December 2002
Available from: 2008-12-16 Created: 2008-12-16 Last updated: 2016-10-04Bibliographically approved
4. Automated implementation of interface- and memory models for real-time video processing systems
Open this publication in new window or tab >>Automated implementation of interface- and memory models for real-time video processing systems
2003 (English)In: Proceedings of IEEE Norchip Conference, November 2003 (Riga), 2003Conference paper, (Refereed)
Abstract [en]

We present a source-code generator for real-time video processing systems that automatically optimise the cache and scheduler performance for selected target architectures. Code can be directly generated from a modelled neighbourhood without any additional data dependency analysis. Experimental results show that almost all data cache misses are removed and we can see a reduction of the execution time in the order of 25 percent compared to non-tuned code. The source-code generator is a part of an automated and target independent development trajectory and motivated by improved designer productivity.

Keyword
real-time image processing, processor architecture
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-1831 (URN)586 (Local ID)586 (Archive number)586 (OAI)
Available from: 2008-09-30 Created: 2008-09-30Bibliographically approved
5. Polyhedral space generation and memory estimation from interface and memory models of real-time video systems
Open this publication in new window or tab >>Polyhedral space generation and memory estimation from interface and memory models of real-time video systems
Show others...
2006 (English)In: Journal of Systems and Software, ISSN 0164-1212, E-ISSN 1873-1228, Vol. 79, no 2, 231-245 p.Article in journal (Refereed) Published
Abstract [en]

We present a tool and a methodology for estimating the memory storage requirement for synchronous real-time video processing systems. Typically, a designer will use the feedback information from this estimation to select the most optimal execution order for software processors or space to time mapping for hardware. We propose to start from a conceptual interface and memory model that captures memory usage and data transfers. This high-level modeling is provided as an extension library of SystemC called IMEM. A common polyhedral iteration space is generated from the model, where polytopes are placed using a new placement algorithm based on simple heuristics. This algorithm will ensure maximum freedom of selecting executing order as all negative dependencies are removed to the length of zero. A demonstration is given regarding how the polytopes and dependency vectors can then be used as input to a memory storage estimation tool called STOREQ.

Keyword
Memory storage estimation, polyhedral, polytope placement, modeling, real-time, video, SystemC
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-2908 (URN)10.1016/j.jss.2005.04.034 (DOI)000235818400008 ()2-s2.0-32544459769 (Scopus ID)2575 (Local ID)2575 (Archive number)2575 (OAI)
Projects
STC - Sensible Things that Communicate
Available from: 2008-09-30 Created: 2009-07-10 Last updated: 2016-09-27Bibliographically approved
6. A Comparison between Local and Global Memory Allocation for FPGA Implementation of Real-Time Video Processing Systems
Open this publication in new window or tab >>A Comparison between Local and Global Memory Allocation for FPGA Implementation of Real-Time Video Processing Systems
2004 (English)In: Proceedings of the IEEE International Conference on Signals and Electronic Systems, 2004Conference paper, (Refereed)
Abstract [en]

This paper presents a comparison of local and global memory allocation for implementation of real-time video processing systems on FPGAs. The paper compares new methods to perform memory allocation using single and dual port block RAMs to memory allocation methods found in the literature. This investigation shows that the use of global allocation can reduce the memory size by up to 75 % for the two presented video processing systems.

Keyword
FPGA, real-time video, memory allocation
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-2379 (URN)1973 (Local ID)1973 (Archive number)1973 (OAI)
Available from: 2008-09-30 Created: 2008-12-16Bibliographically approved
7. Optimization of memory allocation for real-time video processing on FPGA
Open this publication in new window or tab >>Optimization of memory allocation for real-time video processing on FPGA
2005 (English)In: 16th International Workshop on Rapid System Prototyping, Proceedings - SHORTENING THE PATH FROM SPECIFICATION TO PROTOTYPE, IEEE conference proceedings, 2005, Vol. 2005, 141-147 p.Conference paper, (Refereed)
Abstract [en]

We present an optimization model for the allocation of shift registers to dual ported FPGA memory blocks. Shift registers are used in real-time video processing for the storage of data flow dependencies. The model is formalized into a mixed integer linear program that can be executed using a general solver. Allocation results from realistic video systems verify the correctness of the model. This model serves as a formal specification and setup for the development of an efficient allocation heuristic.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2005
Keyword
Computer science
National Category
Computer Science Mathematics Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-3147 (URN)10.1109/RSP.2005.35 (DOI)000230459100020 ()2299 (Local ID)0-7695-2361-7 (ISBN)2299 (Archive number)2299 (OAI)
Conference
16th IEEE International Workshop on Rapid System Prototyping, Jun 08-10, 2005, Montreal, Canada
Projects
STC - Sensible Things that Communicate
Available from: 2008-09-30 Created: 2009-07-30 Last updated: 2012-02-16Bibliographically approved
8. Impact of Bit-Width specification on the memory hierarchy for a real-time video processing system
Open this publication in new window or tab >>Impact of Bit-Width specification on the memory hierarchy for a real-time video processing system
2006 (English)In: Proceedings -Design, Automation and Test in Europe, DATE, Piscataway, NJ: IEEE conference proceedings, 2006, 750-751 p., 1656989Conference paper, (Refereed)
Abstract [en]

The great variety of pixel dynamics of real-time video processing systems, ranging from color, grayscale or binary pixels, means that a careful design and specification of bit-widths is required. It is obvious that the bit-width specification will affect the total memory storage requirement. However, what is not so obvious is that the bit-width specification will also affect the design of the memory hierarchy, an impact similar for both hardware and software implementations. A real-life surveillance system is introduced, as a demonstration application showing how the optimal allocation of shift registers for the storage of intermediate results is sensitive to bit-widths. From this we conclude, that careful memory hierarchy design where bit-widths are considered can reduce the total on-chip memory storage requirement by 61 percent compared to a non-optimal design.

Place, publisher, year, edition, pages
Piscataway, NJ: IEEE conference proceedings, 2006
Series
Design, Automation and Test in Europe Conference and Expo, ISSN 1530-1591
Keyword
Bit-width, memory hierarchy, polyhedral, video
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-3364 (URN)10.1109/DATE.2006.244095 (DOI)000243721600152 ()2-s2.0-34047167028 (Scopus ID)3334 (Local ID)978-3-9810801-1-7 (ISBN)3334 (Archive number)3334 (OAI)
Conference
Design, Automation and Test in Europe, DATE'06; Munich; Germany; 6 March 2006 through 10 March 2006
Projects
STC - Sensible Things that Communicate
Available from: 2008-09-30 Created: 2009-07-29 Last updated: 2016-10-04Bibliographically approved
9. Bit-Width Constrained Memory Hierarchy Optimization for Real-Time Video Systems
Open this publication in new window or tab >>Bit-Width Constrained Memory Hierarchy Optimization for Real-Time Video Systems
Show others...
2007 (English)In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, ISSN 0278-0070, E-ISSN 1937-4151, Vol. 26, no 4, 781-800 p.Article in journal (Refereed) Published
Abstract [en]

The great variety of pixel dynamics of real-time video processing systems, ranging from color, grayscale or binary pixels, means that a careful design and specification of bit-widths is required. It is obvious that the bit-width specification will affect the total memory storage requirement. However, what is not so obvious is that the bit-width specification will also affect the design of the memory hierarchy, an impact similar for both hardware and software implementations. We have developed an Integer Non Linear Program (INLP) formulation for the optimization of the memory hierarchy of real-time video processing systems. An active surveillance video camera is introduced as a test case. We demonstrate how the optimization model can reduce the on-chip memory storage by 61 percent compared to a non optimal memory hierarchy.

Keyword
Bit-width, memory hierarchy, polyhedral, video
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:miun:diva-3847 (URN)10.1109/TCAD.2006.884569 (DOI)000245190500016 ()2-s2.0-33947595234 (Scopus ID)4104 (Local ID)4104 (Archive number)4104 (OAI)
Projects
STC - Sensible Things that Communicate
Note

VR-Computer Science

Available from: 2008-09-30 Created: 2009-07-29 Last updated: 2016-10-04Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Thörnberg, Benny
By organisation
Department of Information Technology and Media
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

Total: 1250 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf