<p>Synthetic antenna aperture (SAR) is a pulses focusing airborne radar which can achieve high resolution radar image. A number of image process algorithms have been developed for this kind of radar, but the calculation burden is still heavy. So the image processing of SAR is normally performed “off-line”.</p><p>The Fast Factorized Back Projection (FFBP) algorithm is considered as a computationally efficient algorithm for image formation in SAR, and several applications have been implemented which try to make the process “on-line”.</p><p>CELL Broadband Engine is one of the newest multi-core-processor jointly developed by Sony, Toshiba and IBM. CELL is good at parallel computation and floating point numbers, which all fit the demands of SAR image formation.</p><p>This thesis is going to implement FFBP algorithm on CELL Broadband Engine, and compare the results with pre-projects. In this project, we try to make it possible to perform SAR image formation in real-time.</p>

In the last years multilevel preconditioners like BPX became more and more popular for solving second-order elliptic finite element discretizations by iterative methods. P. Oswald has adapted these methods for discretizations of the fourth order biharmonic problem by rectangular conforming Bogner-Fox-Schmidt elements and nonconforming Adini elements and has derived optimal estimates for the condition numbers of the preconditioned linear systems. In this paper we generalize the results from Oswald to the construction of BPX and Multilevel Diagonal Scaling (MDS-BPX) preconditioners for the elasticity problem of thin smooth shells of arbitrary forms where we use Koiter's equations of equilibrium for an homogeneous and isotropic thin shell, clamped on a part of its boundary and loaded by a resultant on its middle surface. We use the two discretizations mentioned above and the preconditioned conjugate gradient method as iterative method. The parallelization concept is based on a non-overlapping domain decomposition data structure. We describe the implementations of the multilevel preconditioners. Finally, we show numerical results for some classes of shells like plates, cylinders, and hyperboloids.

Multiphase flow is a familiar phenomenon from daily life and occupies an important role in physics, engineering, and medicine. The understanding of multiphase flows relies largely on the theory of interfaces, which is not well understood in many cases. To date, the Navier-Stokes-Korteweg equations and the Cahn-Hilliard equation have represented two major branches of phase-field modeling. The Navier-Stokes-Korteweg equations describe a single component fluid material with multiple states of matter, e.g., water and water vapor; the Cahn-Hilliard type models describe multi-component materials with immiscible interfaces, e.g., air and water. In this dissertation, a unified multiphase fluid modeling framework is developed based on rigorous mathematical and thermodynamic principles. This framework does not assume any ad hoc modeling procedures and is capable of formulating meaningful new models with an arbitrary number of different types of interfaces. In addition to the modeling, novel numerical technologies are developed in this dissertation focusing on the Navier-Stokes-Korteweg equations. First, the notion of entropy variables is properly generalized to the functional setting, which results in an entropy-dissipative semi-discrete formulation. Second, a family of quadrature rules is developed and applied to generate fully discrete schemes. The resulting schemes are featured with two main properties: they are provably dissipative in entropy and second-order accurate in time. In the presence of complex geometries and high-order differential terms, isogeometric analysis is invoked to provide accurate representations of computational geometries and robust numerical tools. A novel periodic transformation operator technology is also developed within the isogeometric context. It significantly simplifies the procedure of the strong imposition of periodic boundary conditions. These attributes make the proposed technologies an ideal candidate for credible numerical simulation of multiphase flows. A general-purpose parallel computing software, named PERIGEE, is developed in this work to provide an implementation framework for the above numerical methods. A comprehensive set of numerical examples has been studied to corroborate the aforementioned theories. Additionally, a variety of application examples have been investigated, culminating with the boiling simulation. Importantly, the boiling model overcomes several challenges for traditional boiling models, owing to its thermodynamically consistent nature. The numerical results indicate the promising potential of the proposed methodology for a wide range of multiphase flow problems. / text

Οι συστάδες υπολογιστών αποτελούν μία σύγχρονη ευρέως χρησιμοποιούμενη και ιδιαίτερα ανταγωνιστική αρχιτεκτονική για την υλοποίηση υπολογιστικών συστημάτων υψηλών επιδόσεων με χαμηλό κόστος. Παράλληλα, η ευρεία εμπορική διάθεση πολυεπεξεργαστικών συστημάτων μικρής κλίμακας, επιτρέπει τον συνδυασμό τους σε υβριδικά σχήματα συστάδων πολυεπεξεργαστών. Παρά την ευελιξία που παρέχεται στη σχεδίαση τους, η απαίτηση για χρήση κατανεμημένων μοντέλων προγραμματισμού αυξάνει σημαντικά την πολυπλοκότητα της ανάπτυξης εφαρμογών. Μία εναλλακτική προσέγγιση αποτελούν τα συστήματα κοινής ιδεατής μνήμης. Τα συστήματα κοινής ιδεατής μνήμης παρέχουν στις εφαρμογές, που εκτελούνται σε διαφορετικούς κόμβους της συστάδας, πρόσβαση σε έναν διαμοιραζόμενο χώρο διευθύνσεων αποκρύπτοντας την υποκείμενη κατανεμημένη αρχιτεκτονική. Βασικότερο περιορισμό της πλειονότητας των υπαρχόντων υλοποιήσεων αποτελεί η απουσία υποστήριξης πολυνηματισμού. Το χαρακτηριστικό αυτό έχει ως άμεση συνέπεια τη χαμηλή χρησιμοποίηση των σύγχρονων πολυεπεξεργαστικών υπολογιστικών μονάδων, καθώς ούτε η εφαρμογή αλλά ούτε και οι μηχανισμοί που εξασφαλίζουν τη συνέπεια της κοινής μνήμης εκτελούνται παράλληλα. Στα πλαίσια της παρούσας μεταπτυχιακής εργασίας παρουσιάζεται η σχεδίαση και η υλοποίηση μίας πλατφόρμας κοινής ιδεατής μνήμης χρησιμοποιώντας μηχανισμούς υλοποιημένους αποκλειστικά σε λογισμικό. Το προτεινόμενο σύστημα στοχεύει στην αποδοτικότερη χρησιμοποίηση των πόρων των πολυεπεξεργαστικών μονάδων της συστάδας, υποστηρίζοντας την πολυνηματική εκτέλεση της εφαρμογής σε κάθε κόμβο. Τόσο το πρωτόκολλο συνέπειας της κατανεμημένης μνήμης, όσο και το υποσύστημα επικοινωνίας, επανασχεδιάστηκαν ώστε να χρησιμοποιούν πολλαπλά νήματα εκτέλεσης. Επιπλέον παρουσιάζονται και αξιολογούνται εναλλακτικοί ιεραρχικοί αλγόριθμοι συγχρονισμού που επιτρέπουν την αποδοτικότερη χρήση της υβριδικής οργάνωσης των συστάδων. / Software Distributed Shared Memory (SDSM) systems provide an abstraction layer of shared memory semantics on top of a distributed set of computational nodes. The use of small-scale Symmetric Multiprocessor (SMP) nodes has the potential for bridging the performance-cost gap between the low-end SMPs and high-end Distributed Shared Memory (DSM) systems, using a hybrid software and hardware coherency model presented in this thesis. We present the design and discuss the main architectural choices involved in our implementation of a multithreaded SDSM system. Our implementation was developed on top of Pthreads and the TCP/IP network protocol, employing a simple yet efficient design. Finally, we evaluate and analyze the performance of the multithreading SDSM platform, using a wide set of benchmark applications.

This thesis develops efficient modeling frameworks via a Partial Differential Equation (PDE) approach for multi-factor financial derivatives, with emphasis on three-factor models, and studies highly efficient implementations of the numerical methods on novel high-performance computer architectures, with particular focus on Graphics Processing Units (GPUs) and multi-GPU platforms/clusters of GPUs. Two important classes of multi-factor financial instruments are considered: cross-currency/foreign exchange (FX) interest rate derivatives and multi-asset options. For cross-currency interest rate derivatives, the focus of the thesis is on Power Reverse Dual Currency (PRDC) swaps with three of the most popular exotic features, namely Bermudan cancelability, knockout, and FX Target Redemption. The modeling of PRDC swaps using one-factor Gaussian models for the domestic and foreign interest short rates, and a one-factor skew model for the spot FX rate results in a time-dependent parabolic PDE in three space dimensions. Our proposed PDE pricing framework is based on partitioning the pricing problem into several independent pricing subproblems over each time period of the swap's tenor structure, with possible communication at the end of the time period. Each of these subproblems requires a solution of the model PDE. We then develop a highly efficient GPU-based parallelization of the Alternating Direction Implicit (ADI) timestepping methods for solving the model PDE. To further handle the substantially increased computational requirements due to the exotic features, we extend the pricing procedures to multi-GPU platforms/clusters of GPUs to solve each of these independent subproblems on a separate GPU. Numerical results indicate that the proposed GPU-based parallel numerical methods are highly efficient and provide significant increase in performance over CPU-based methods when pricing PRDC swaps. An analysis of the impact of the FX volatility skew on the price of PRDC swaps is provided. In the second part of the thesis, we develop efficient pricing algorithms for multi-asset options under the Black-Scholes-Merton framework, with strong emphasis on multi-asset American options. Our proposed pricing approach is built upon a combination of (i) a discrete penalty approach for the linear complementarity problem arising due to the free boundary and (ii) a GPU-based parallel ADI Approximate Factorization technique for the solution of the linear algebraic system arising from each penalty iteration. A timestep size selector implemented efficiently on GPUs is used to further increase the efficiency of the methods. We demonstrate the efficiency and accuracy of the proposed GPU-based parallel numerical methods by pricing American options written on three assets.

Praktikoje dažnai tenka spręsti sudėtingus daugiakriterinius optimizavimo uždavinius, kai kriterijai būna prieštaringi, o galutinis apsisprendimas priklauso nuo sprendimų priėmėjo. Kai sprendimų priėmėjas dalyvauja sprendimo procese interaktyviai, tai jis gali koreguoti prioritetus ir siekiamus tikslus uždavinio sprendimo eigoje, kas įgalina spęsti uždavinius, turinčius daug kriterijų ir apribojimų. Be to, sprendimo priėmėjui svarbu gauti sprendinius iš visos Pareto aibės. Interaktyviam uždavinių sprendimui būtina sprendimų paramos sistema, kurios grafinė sąsaja yra pritaikyta sprendžiamam uždaviniui. Šio darbo tyrimų sritis yra interaktyvus daugiakriterinių optimizavimo uždavinių sprendimas bei sprendimų paramos sistemos. Disertacijoje nagrinėjant daugiakriterinio optimizavimo metodus, didesnis dėmesys skirtas metodams, užtikrinantiems gaunamų sprendinių tolygų pasiskirstymą Pareto aibėje bei interaktyviems metodams. Pasiūlytas ir ištirtas daugiakriterinių optimizavimo uždavinių sprendimo būdas, leidžiantis spręsti daugiakriterinius optimizavimo uždavinius interaktyviai ir užtikrinantis gaunamų sprendinių tolygų pasiskirstymą Pareto aibėje. Sukurta ir ištirta interaktyvi daugiakriterinių optimizavimo uždavinių sprendimų paramos sistemą, apjungianti pasiūlytą optimizavimo uždavinių sprendimo būdą, sprendimo proceso vizualizavimą ir jo lygiagretinimą. Taip pat pasiūlyta sprendimo strategija, pagal kurią sprendžiant daugiakriterinį optimizavimo uždavinį pasitelkiamas... [toliau žr. visą tekstą] / In practice, optimization problems are often multiple criteria. The criteria are usually contradictory, so the final decision depends on a decision maker. When the problem is solved interactively, the decision maker can change his/her preferences in decision process. Moreover, it is important to obtain solutions from the whole Pareto front. A decision support system adapted to the specific of the problem is essential for solving multiple criteria optimization problems interactively. The objects of research are multiple criteria optimization problems, interactive methods for solving these problems, interactive decision support systems, and application of parallel computing in decision support systems. Multiple criteria optimization methods are analyzed in the dissertation. The focus of attention is the methods for a uniform distribution of solutions on the Pareto front as well as the interactive methods. An interactive way for solving multicriteria optimization problems, which finds alternative solutions uniformly distributed on the Pareto front is proposed and investigated in this dissertation. An interactive decision support system which integrates the created interactive solving way, the decision process visualization and parallelization for multiple criteria optimization is developed. The solving strategies, when a multiple criteria optimization problem is solved interactively, using a computer cluster are developed and compared experimentally. The time required for a... [to full text]

In practice, optimization problems are often multiple criteria. The criteria are usually contradictory, so the final decision depends on a decision maker. When the problem is solved interactively, the decision maker can change his/her preferences in decision process. Moreover, it is important to obtain solutions from the whole Pareto front. A decision support system adapted to the specific of the problem is essential for solving multiple criteria optimization problems interactively. The objects of research are multiple criteria optimization problems, interactive methods for solving these problems, interactive decision support systems, and application of parallel computing in decision support systems. Multiple criteria optimization methods are analyzed in the dissertation. The focus of attention is the methods for a uniform distribution of solutions on the Pareto front as well as the interactive methods. An interactive way for solving multicriteria optimization problems, which finds alternative solutions uniformly distributed on the Pareto front is proposed and investigated in this dissertation. An interactive decision support system which integrates the created interactive solving way, the decision process visualization and parallelization for multiple criteria optimization is developed. The solving strategies, when a multiple criteria optimization problem is solved interactively, using a computer cluster are developed and compared experimentally. The time required for a... [to full text] / Praktikoje dažnai tenka spręsti sudėtingus daugiakriterinius optimizavimo uždavinius, kai kriterijai būna prieštaringi, o galutinis apsisprendimas priklauso nuo sprendimų priėmėjo. Kai sprendimų priėmėjas dalyvauja sprendimo procese interaktyviai, tai jis gali koreguoti prioritetus ir siekiamus tikslus uždavinio sprendimo eigoje, kas įgalina spęsti uždavinius, turinčius daug kriterijų ir apribojimų. Be to, sprendimo priėmėjui svarbu gauti sprendinius iš visos Pareto aibės. Interaktyviam uždavinių sprendimui būtina sprendimų paramos sistema, kurios grafinė sąsaja yra pritaikyta sprendžiamam uždaviniui. Šio darbo tyrimų sritis yra interaktyvus daugiakriterinių optimizavimo uždavinių sprendimas bei sprendimų paramos sistemos. Disertacijoje nagrinėjant daugiakriterinio optimizavimo metodus, didesnis dėmesys skirtas metodams, užtikrinantiems gaunamų sprendinių tolygų pasiskirstymą Pareto aibėje bei interaktyviems metodams. Pasiūlytas ir ištirtas daugiakriterinių optimizavimo uždavinių sprendimo būdas, leidžiantis spręsti daugiakriterinius optimizavimo uždavinius interaktyviai ir užtikrinantis gaunamų sprendinių tolygų pasiskirstymą Pareto aibėje. Sukurta ir ištirta interaktyvi daugiakriterinių optimizavimo uždavinių sprendimų paramos sistemą, apjungianti pasiūlytą optimizavimo uždavinių sprendimo būdą, sprendimo proceso vizualizavimą ir jo lygiagretinimą. Taip pat pasiūlyta sprendimo strategija, pagal kurią sprendžiant daugiakriterinį optimizavimo uždavinį pasitelkiamas... [toliau žr. visą tekstą]

We study the facial structure of the independent set polytope using the concept of conflict hypergraphs. A conflict hypergraph is a hypergraph whose vertices correspond to the binary variables, and edges correspond to covers in the constraint matrix of the independent set polytope. Various structures such as cliques, odd holes, odd anti-holes, webs and anti-webs are identified on the conflict hypergraph. These hypergraph structures are shown to be generalization of traditional graph structures. Valid inequalities are derived from these hypergraph structures, and the facet defining conditions are studied. Chvatal-Gomory ranks are derived for odd hole and clique inequalities. To test the hypergraph cuts, we conduct computational experiments on market-share (also referred to as market-split) problems. These instances consist of 100% dense multiple-knapsack constraints. They are small in size but are extremely hard to solve by traditional means. Their difficult nature is attributed mainly to the dense and symmetrical structure. We employ a special branching strategy in combination with the hypergraph inequalities to solve many of the particularly difficult instances. Results are reported for serial as well as parallel implementations.

Analyzing massive-data sets and streams is computationally very challenging. Data sets in systems biology, network analysis and security use network abstraction to construct large-scale graphs. Graph algorithms such as traversal and search are memory-intensive and typically require very little computation, with access patterns that are irregular and fine-grained. The increasing streaming data rates in various domains such as security, mining, and finance leaves algorithm designers with only a handful of clock cycles (with current general purpose computing technology) to process every incoming byte of data in-core at real-time. This along with increasing complexity of mining patterns and other analytics puts further pressure on already high computational requirement. Processing streaming data in finance comes with an additional constraint to process at low latency, that restricts the algorithm to use common techniques such as batching to obtain high throughput. The primary contributions of this dissertation are the design of novel parallel data analysis algorithms for graph traversal on large-scale graphs, pattern recognition and keyword scanning on massive streaming data, financial market data feed processing and analytics, and data transformation, that capture the machine-independent aspects, to guarantee portability with performance to future processors, with high performance implementations on multicore processors that embed processorspecific optimizations. Our breadth first search graph traversal algorithm demonstrates a capability to process massive graphs with billions of vertices and edges on commodity multicore processors at rates that are competitive with supercomputing results in the recent literature. We also present high performance scalable keyword scanning on streaming data using novel automata compression algorithm, a model of computation based on small software content addressable memories (CAMs) and a unique data layout that forces data re-use and minimizes memory traffic. Using a high-level algorithmic approach to process financial feeds we present a solution that decodes and normalizes option market data at rates an order of magnitude more than the current needs of the market, yet portable and flexible to other feeds in this domain. In this dissertation we discuss in detail algorithm design challenges to process massive-data and present solutions and techniques that we believe can be used and extended to solve future research problems in this domain.

Les études menées dans cette thèse portent sur le rôle de la couleur dans l'attention visuelle. Nous avons tenté de comprendre l'influence de l'information couleur dans les vidéos sur les mouvements oculaire, afin d'intégrer les attributs couleur dans un modèle de saillance visuelle. Pour cela, nous avons analysé différentes caractéristiques des mouvements oculaires d'observateurs regardant librement des vidéos en deux conditions: couleur et niveaux de gris. Nous avons également comparé les régions principales de regard sur des vidéos en couleur avec celles en niveaux de gris. Il est apparu que les informations de couleur modifient légèrement les caractéristiques de mouvement oculaire comme la position de l'œil et la durée des fixations. Cependant, nous avons constaté que la couleur augmente le nombre de régions de regard. De plus, cet influence de la couleur s'accroît au cours du temps. En nous appuyant sur ces résultats, nous avons proposé une méthode de calcul des cartes de saillance couleur. Nous avons intégré ces cartes dans un modèle de saillance existant. / The studies conducted in this thesis focus on the role of colour in visual attention. We tried to understand the influence of colour information on the eye movements while observing videos, to incorporate colour information into a model of visual saliency. For this, we analysed different characteristics of eye movements of observers while freely watching videos in two conditions: colour and grayscale videos. We also have compared the main regions of regard of colour videos with those of grayscale. We observed that colour information influences only moderately, the eye movement characteristics such as the position of gaze and duration of fixations. However, we found that colour increases the number of the regions of interest in video stimuli. Moreover, this varies across time. Based on these observations, we proposed a method to compute colour saliency maps for videos. We have incorporated colour saliency maps in an existing model of saliency.