Orientadores: Aurelio Ribeiro Leite de Oliveira, Christiano Lyra Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T10:57:39Z (GMT). No. of bitstreams: 1 Cantane_DanielaRenata.pdf: 1253133 bytes, checksum: 870b16a2b9360f77ebd88f50491d181c (MD5) Previous issue date: 2009 / Resumo: A solução eficiente de sistemas lineares é fundamental em problemas de otimização linear e o primeiro método a obter êxito nesta classe de problemas foi o método Simplex. Com o objetivo de desenvolver alternativas eficientes para sua implementação, são apresentadas nesta tese técnicas de atualização da decomposição LU da base para aperfeiçoar a solução dos sistemas lineares oriundos do método Simplex, utilizando um reordenamento estático nas colunas da matriz. Uma simulação do método Simplex é implementada, realizando troca de bases obtidas pelo MINOS e verificando sua esparsidade. Somente os elementos afetados pela mudança de base são considerados para obter uma atualização da decomposição LU eficaz. As colunas da matriz são reordenadas de acordo com três estratégias: mínimo grau; forma bloco triangular e estratégia de Björck. Assim, obtém-se uma decomposição esparsa para qualquer base sem esforço computacional para obter a ordem das colunas, pois o reordenamento da matriz é estático e as colunas da base obedecem esta ordem. A forma bloco triangular obteve os melhores resultados, para os maiores problemas testados, em relação ao mínimo grau e a estratégia de Björck. Resultados computacionais para problemas da Netlib mostram a robustez e um bom desempenho computacional do método de atualização da decomposição LU proposto, pois não são necessárias refatorações periódicas da base como nos métodos de atualização tradicionais. O método proposto obteve uma redução do número de elementos não nulos da base em relação ao MINOS. Esta abordagem foi aplicada em problemas de corte de estoque e a atualização da decomposição LU proposta obteve uma redução do tempo computacional na solução destes problemas em relação ao GPLK. / Abstract: Finding efficient solution of linear systems is fundamental in the linear programming problems and the first method to obtain success for this class of problems was the Simplex method. With the objective to develop efficient alternatives to its implementation, techniques of the simplex basis LU factorization update are developed in this thesis to improve the solution of the Simplex method linear systems towards a matrix columns static reordering. A simulation of the Simplex method is implemented, carrying through the change of basis obtained from MINOS and verifying its sparsity. Only the factored columns actually modified by the change of the base are carried through to obtain an efficient LU factorization update. The matrix columns are reordered according to three strategies: minimum degree; block triangular form and the Björck strategy. Thus, sparse factorizations are obtained for any base without computational effort to obtain the order of columns, since the reordering of the matrix is static and base columns follow this ordering. The application of the block triangular form achieved the best results, for larger scale problems tested, in comparison to minimum degree method and the Björck strategy. Computational results for Netlib problems show the robustness of this approach and good computational performance, since there is no need of periodical factorizations as used in traditional updating methods. The proposed method obtained a reduction of the nonzero entries of the basis with respect to MINOS. This approach was applied in the cutting stock problems and the proposed method achieved a reduction of the computational time in the solution of such problems with respect to the GLPK. / Universidade Estadual de Campi / Automação / Doutor em Engenharia Elétrica

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第22862号 / 情博第741号 / 新制||情||127(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 太田 快人, 教授 鹿島 久嗣 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Der Vortrag gibt einen Überblick zu RPM als Paketverwaltung für Unix/Linux-Systeme. Der Bau von RPM-Paketen wird an einem einfachen Beispiel skizziert. Paketverwaltungswerkzeuge (yum) werden vorgestellt.

In diesem Vortrag wird die Weiterentwicklung von Mathcad gezeigt. Einmal als Update auf Mathcad 15 und dann die ganz neue Generation Mathcad Prime, mit neuer Benutzeroberfläche und neuem "look and feel". Sowie die neuen Funktionen und Möglichkeiten in Mathcad Prime.

As mobile phones get increasingly complicated the demands for an effective firmware update service increase. A proposed solution is Firmware Over The Air (FOTA) and the Open Mobile Alliance’s Device Management where mobile phones can be updated and managed via the mobile phone network. However, before these operations can be carried out, all FOTA capable mobile phones that should be served must be discovered and registered with a distributor of updates. The information provided must be sufficient to uniquely identify devices, initiate a Device Management session, and determine if a firmware update is needed. This thesis addresses the problems that a solution in automatically collecting this information. Several solutions are presented and their suitability evaluated on the basis of defined and analyzed requirements. The solutions most thoroughly examined are various manual solutions, retrieval of information from core network nodes, and utilizing the Short Message Service (SMS) or Unstructured Supplementary Service Data (USSD). A phone application has been implemented according to the requirements from the Chinese network operator China Mobile Communications Corporation (CMCC). It is a part of a solution in which the information is delivered via a SMS session. The design and development phase of the application is described, accompanied by a brief description of the Symbian OS and the working environment (tools, devices, etc.) needed to implement this solution. This work took place at the Sony Ericsson office in Beijing, China. The application implemented is robust and it is impossible to avoid registration, furthermore the user can not be exposed to acknowledgement messages. It has been made possible on the cost of decreased phone performance (a few kB of memory) since the application runs all the time. Malfunctioning phone or network may hinder registration. / Mobiltelefoner blir ständigt mer komplicerade vilket medför att efterfrågan av en effektiv lösning för uppdateringar av mjukvaran i mobiltelefonerna ökar. Lösningen är Firmware Over The Air (FOTA) och Device Management; mobiltelefonerna uppdateras och sköts via mobiltelefonnätverket. Men innan förfaranden kan exekveras måste alla mobiltelefoner med FOTA som ska omfattas av tjänsten upptäckas och registreras hos den som distribuerar uppdateringarna. Den information som måste levereras måste vara tillräcklig för att kunna identifiera mobiltelefonen, genomföra en Device Management session och avgöra om en uppdatering av mjukvaran är nödvändig. Detta examensarbete behandlar de problem som en lösning i vilken information tillhandahålls möter. Ett flertal lösningar presenteras och deras lämplighet utvärderas på basis av definierade och analyserade krav. De mest ingående undersökta lösningarna är olika manuella lösningar, insamling av information från noderna av kärnnätverket samt utnyttjande av SMS eller USSD. En telefonapplikation har implementeras enligt krav från den kinesiska operatören CMCC. Applikationen är en del av en lösning i vilken informationen levereras via en SMS-session. Applikationens design och utvecklingsfasen är beskriven, samt en översiktlig beskrivning av Symbian operativsystem och utvecklingsmiljön (verktyg, mobiltelefoner, etc.) som behövdes för att implementera lösningen. Detta arbete genomfördes på Sony Ericssons kontor i Beijing, Kina.

<p>Real-time global illumination has been a very important topic and is widely used in game industry. Previous offline rendering requires a large amount of time to converge and reduce the noise generated in Monte Carlo method. Thus, it cannot be easily adapted in real-time rendering. Using voxels in the field of global illumination has become a popular approach. While a naïve voxel grid occupies huge memory in video card, a data structure called <i>sparse voxel octree</i> is often implemented in order to reduce memory cost of voxels and achieve efficient ray casting performance in an interactive frame rate. </p> <p>However, rendering of voxels can cause block effects due to the nature of voxel. One solution is to increase the resolution of voxel so that one voxel is smaller than a pixel on screen. But this is usually not feasible because higher resolution results in higher memory consumption. Thus, most of the global illumination methods of SVO (sparse voxel octree) only use it in visibility test and radiance storage, rather than render it directly. Previous research has tried to incorporate SVO in ray tracing, radiosity methods and voxel cone tracing, and all achieved real-time frame rates in complex scenes. However, most of them only focus on static scenes and does not consider dynamic updates of SVO and the influence of it on performance.</p> <p>In this thesis, we will discuss the tradeoff of multiple classic real-time global illumination methods and their implementations using SVO. We will also propose an efficient approach to dynamic update SVO in animated scenes. The deliverables will be implemented in CUDA 11.0 and OpenGL.</p>

We present an implementation of a very recent approximation algorithm for scheduling jobs on a single machine with precedence constraints, minimising the total weighted completion time. We also evaluate the performance of this implementation. The algorithm was published by Shi Li in 2021 and is a (6+ε)-approximation algorithm for the multiprocessor problem P|prec|∑j wjCj. We have implemented a version which is a (2+ε)-approximation algorithm for the single processor problem 1|prec|∑j wjCj. This special case can easily be generalised to the multiprocessor case, as the two algorithms are based on the same LP relaxation of the problem. Unlike other approximation algorithms for this and similar problems, for example, those published by Hall, Schulz, Shmoys and Wein in 1997, and by Li in 2020, this algorithm has been developed with a focus on obtaining a good asymptotic run time guarantee, rather than obtaining the best possible guarantee on the quality of solutions. Li’s algorithm has run time O((n+κ) · polylog(n+κ) · log3 pmax · 1/ε2), where n is the number of jobs, κ is the number of precedence constraints and pmax is the largest of the processing times of the jobs. We also present a detailed explanation of the algorithm aimed at readers who do not necessarily have a background in scheduling and/or approximation algorithms, based on the paper by Li. Finally, we empirically evaluate how well (our implementation of) this algorithm performs in practice. The performance was measured on a set of 96 randomly generated instances, with the largest instance having 1024 jobs and 32 768 precedence constraints. We can find a solution for an instance with 512 jobs and 11 585 precedence constraints in 25 minutes. / Vi presenterar en praktisk implementation av en ny approximationsalgoritm för schemaläggning av jobb på en maskin med ordningsbivillkor, under minimering av den viktade summan av sluttider. Algoritmen, som publicerades av Shi Li år 2021, är en (6+ε)-approximationsalgoritm för multiprocessorproblemet P|prec|∑j wjCj. Vi har implementerat en version som är en (2+ε)-approximationsalgoritm för enprocessorproblemet 1|prec|∑j wjCj. Detta specialfall kan enkelt generaliseras till multiprocessorfallet, eftersom de två algoritmerna baseras på samma LP-relaxation av problemet. Till skillnad från andra approximationsalgoritmer för detta och liknande problem, exempelvis de från Hall, Schulz, Shmoys och Wein år 1997, och från Li år 2020, har denna algoritm utvecklats med fokus på att uppnå en bra garanti på asymptotisk körtid, istället för att försöka uppnå den bästa möjliga garantin på lösningarnas kvalité. Lis algoritm har körtid O((n+κ) · polylog(n+κ) · log3 pmax · 1/ε2), där n är antalet jobb, κ antalet ordningsbivillkor och pmax är den största körtiden bland jobben. En detaljerad beskrivning av algoritmen riktad till personer som inte nödvändigtvis har förkunskaper inom schemaläggning och/eller approximationsalgoritmer, baserad på artikeln, ges också. Slutligen utvärderar vi empiriskt hur väl (vår implementation av) denna algoritm presterar i praktiken. Implementationens egenskaper mättes på en uppsättning av 96 slumplässigt genererade instanser, där den största instansen har 1024 jobb och 32768 ordningsbivillkor. Med vår implementation kan vi hitta en lösning för en instans med 512 jobb och 11 585 precedencensbivillkor på 25 minuter.

No description available.

Software Defined Networking (SDN) emerged in recent years to fundamentally change how we design, build and manage networks. To maximize the network utilization, its control plane needs to frequently update the data plane via flow migration as the network conditions change dynamically, which is known as network update. Network Function Virtualization (NFV) addresses the problems of traditional expensive hardware appliances by leveraging virtualization technology to implement network functions in software modules (middleboxes). These software modules, also called Virtual Network Functions (VNFs), are provisioned most commonly in modern networks to demonstrate their increasing importance. The technical combination of SDN and NFV enables network service providers to pick service locations from multiple available servers and maneuvers traffic through appropriate VNFs, which is known as VNF deployment. A service chain consists of multiple chained VNFs in some order. VNFs are executed on virtualization platforms, which makes them more prone to error compared with dedicated hardware. As a result, one important issue of service chain is its reliability, meaning that each type of VNF in a service chain acts properly on its function, which is known as service chain resilience. This dissertation lists our research on the above three mentioned topics in order to improve the network performance. Details are as follows: 1. Network Update: SDNs always need to migrate flows to update the network configuration for a better system performance. However, the existing literature does not take flow path overlapping information into consideration when flows’ routes are re-allocated. Consequently, congestion happens, resulting in deadlocks among flows and link resources, which will block the update process and cause severe packet loss. We propose multiple solutions with various kinds of leisure resources in the network. 2. VNF Deployment: We focus on the VNF deployment problem with different settings and constraints, including: (1) network topology; (2) vertex capacity constraint; (3) traffic-changing effect; (4) heterogeneous or homogeneous model for one VNF kind; (5) dependency relations between VNFs. We efficiently deploy VNF instances and at the same time make sure that the processing requirement of all flows are satisfied. 3. Resilient Service Chain Management: One effective way of ensuring VNF robustness is to provision redundancy in the form of deploying backup instances besides active ones. In order to guarantee the service chain reliability, we consider both the server resource allocation and the VNF backup assignment. We aim at minimizing the total cost in terms of transmission delay and rule changes. / Computer and Information Science

The dramatic increase in the amount of content available in digital forms gives rise to large-scale digital libraries, targeted to support millions of users and terabytes of data. Retrieving information from a system of this scale in an efficient manner is a challenging task due to the size of the collection as well as the index. This research deals with the design and implementation of an inverted index that supports searching for information in a large-scale digital library, implemented atop a massively parallel storage system. Inverted index partitioning is studied in a simulation environment, aiming at a terabyte of text. As a result, a high performance partitioning scheme is proposed. It combines the best qualities of the term and document partitioning approaches in a new Hybrid Partitioning Scheme. Simulation experiments show that this organization provides good performance over a wide range of conditions. Further, the issues of creation and incremental updates of the index are considered. A disk-based inversion algorithm and an extensible inverted index architecture are described, and experimental results with actual collections are presented. Finally, distributed algorithms to create a parallel inverted index partitioned according to the hybrid scheme are proposed, and performance is measured on a portion of the equipment that normally makes up the 100 node Virginia Tech PetaPlex™ system. NOTE: (02/2007) An updated copy of this ETD was added after there were patron reports of problems with the file. / Ph. D.