Show simple item record

dc.contributor.advisorMilovanović, Igor Ž.
dc.contributor.otherMilovanović, Emina I.
dc.contributor.otherKocić, Ljubiša M.
dc.contributor.otherĐorđević, Dragan S.
dc.contributor.otherNikolić, Zoran S.
dc.creatorRanđelović, Branislav M.
dc.date.accessioned2016-11-20T17:03:28Z
dc.date.available2016-11-20T17:03:28Z
dc.date.available2020-07-03T16:03:08Z
dc.date.issued2015-06-03
dc.identifier.urihttp://eteze.ni.ac.rs/application/showtheses?thesesId=4200
dc.identifier.urihttp://nardus.mpn.gov.rs/handle/123456789/7063
dc.identifier.urihttps://fedorani.ni.ac.rs/fedora/get/o:1139/bdef:Content/download
dc.identifier.urihttp://vbs.rs/scripts/cobiss?command=DISPLAY&base=70052&RID=533829526
dc.description.abstractEach algorithm uniquely corresponds to a directed graph, and each parallel computer system, also uniquely corresponds to a directed graph. Therefore, solving many problems regarding algorithms and parallel computer systems, is reduced to solving problems on the graph level. In this thesis, we deal with the problem how to determine a mapping of graph of algorithm, which corresponds to a given problem, so that the result of mapping is a graph of corresponding parallel computer system, on which the problem is going to be effectively implemented. Practically, on the basis of the algorithm of problem, we design a parallel computer system of special purpose, suitable for solving the problem. The main topic of interest in this thesis are 3D coordinate graphs, as well as possibilities of their mapping to the plane (2D) and line (1D). The geometrical relationship between three-dimensional objects and their two-dimensional images, ie. projections in some planes, is very important and has many applications in various fields of science and technology. During determination of those mappings, principle of neighborhoods between nodes in a given graph and in its image has to be preserved, and also minimal number of nodes in a graph, which corresponds to a parallel computer system. Without loss of generality, we deal with graphs that can be presented in a three-dimensional coordinate system. This thesis gives an answer to the question how the three-dimensional mesh, ie. coordinate graph, maps to a plane and a line. First, we determine all possible projection directions for design, with respect to certain limitations. For each possible projection direction we define the mapping, which ensures that the resulting image have the optimal number of nodes, taking into account that principle of neighborhood between nodes is preserved. Beside compilation of previous results, the main results and contributions of this thesis has been provided via formal mathematical forms through 1 lemma, 7 theorems and 3 corollaries. The most important theorems, that are base of whole process of projection of coordinate graphs are given with complete proofs. These theorems are still not published and they represents an original contribution of this thesis. In other parts of the dissertation, using introduced mapping, we design all possible 1D systolic arrays for solving one of the basic and most used problems in linear algebra, matrix product. Then, we implement the same methods for synthesis of 1D systolic arrays for solving some standard problems in graph theory: finding the transitive closure of directed graph, finding all shortest paths between nodes in graph, finding all possible minimum cost spanning trees in a given graph. Several years of research in this area, showed us the path for solving the complete set of tasks. It is shown, first on the theoretical level, and then through all those applications, that method of projection of graphs, introduced in this thesis, is the best, and also enables an automatic synthesis of arrays, through explicit formulas, and also gives optimality of the obtained arrays, in terms of space, or time or space-time.en
dc.formatapplication/pdf
dc.languagesr
dc.publisherУниверзитет у Нишу, Електронски факултетsr
dc.relationinfo:eu-repo/grantAgreement/MESTD/Technological Development (TD or TR)/32012/RS//
dc.relationinfo:eu-repo/grantAgreement/MESTD/Integrated and Interdisciplinary Research (IIR or III)/43007/RS//
dc.rightsopenAccessen
dc.sourceУниверзитет у Нишуsr
dc.subjectkoordinatni grafovisr
dc.subjectcoordinate graphsen
dc.subjectsystolic arraysen
dc.subjectmatrix multiplicationen
dc.subjectgraph algorithmsen
dc.subjectsistolička poljasr
dc.subjectmnoženje matricasr
dc.subjectgrafovski algoritmisr
dc.titleProjektovanje 3D koordinatnih usmerenih grafova na ravan i pravu i primena u procesu sinteze sistoličkih poljasr
dc.typedoctoralThesisen
dc.rights.licenseBY-NC-ND
dcterms.abstractМиловановић, Игор Ж.; Миловановић, Емина И.; Коцић, Љубиша М.; Николић, Зоран С.; Ђорђевић, Драган С.; Ранђеловић, Бранислав М.; Пројектовање 3Д координатних усмерених графова на раван и праву и примена у процесу синтезе систоличких поља; Пројектовање 3Д координатних усмерених графова на раван и праву и примена у процесу синтезе систоличких поља;
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/52448/Randjelovic_Branislav.pdf
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/52447/Disertacija6420.pdf


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record