With the flourishing development of the Internet and progress of science and technology, the wireless network technology is growing up rapidly at present. People can make connections through the Internet whenever and wherever possible. Mobile IPv6 is proposed in order to support mobility in IPv6 network, offers safer and more efficient mobile communication service to users than Mobile IPv4. However, it still suffers long delays and high packet losses. In order to enable smooth handovers, many researches in which use buffering and forwarding methods have been proposed. Although these proposals significantly improve handover performances, they suffer from the out-of-order delivery problem. This paper proposes a scheme which integrates multicast technologies with FMIPv6 for improving the handover performance. By switching between unicast addressing mode and multicast addressing mode, and letting the access router of the new network (NAR) join the multicast group in anticipation during handover, correspondent nodes (CNs) can transmit data packets to the new and old networks of mobile nodes (MNs) directly at the same time. It not only averts the out-of-order delivery problem, but also reduces the effect of the Duplicated Address Detection (DAD) time on the service disruption time.

Modern processors use out-of-order processing logic to achieve high performance in Instructions Per Cycle (IPC) but this logic has a serious impact on the achievable frequency. In order to get better performance out of smaller transistors there is a trend to increase the number of cores per die instead of making the cores themselves bigger. Moreover, for throughput-oriented and server workloads, simpler in-order processors that allow more cores per die and higher design frequencies are becoming the preferred choice. Unfortunately, for other workloads this type of cores result in a lower single thread performance. There are many workloads where it is still important to achieve good single thread performance. In this thesis we present the ReLaSch processor. Its aim is to enable high IPC cores capable of running at high clock frequencies by processing the instructions using simple superscalar in-order issue logic and caching instruction groups that are dynamically scheduled in hardware after commit, that is, out of the critical path and only when really needed. Objective This thesis has several research goals: • Show that the dynamic scheduler of a conventional out-of-order processor does a lot of redundant work because it ignores the repetitiveness of code. • Propose a complete superscalar out-of-order architecture that reduces the amount of redundant work done by creating the schedules once in dedicated hardware, storing them in a cache of schedules and reusing the schedules as much as possible. • Place the scheduler out of the critical path of execution, which should be enabled by the reduction of work that it must do. Thus, the execution path of our proposed processor can be simpler than that of a conventional out-of-order processor. Proposal and results We present the \textbf{ReLaSch} processor, named after Reused Late Schedules, in which the creation of issue-groups is removed from the critical path of execution and uses a simple and small in-order issue logic. It just wakes-up and selects the instructions of a single issue-group each cycle, instead of processing the instructions of a whole issue queue. A new logic at the end of the conventional pipeline schedules the committed instructions. The new scheduler can be complex since it is not in the critical path of execution. The schedules are cached and whenever it is possible an rgroup is read and its instructions executed. The schedules are reused, lowering the pressure on the scheduling logic. In some cases, the ReLaSch processor is able to outperform a conventional out-of-order processor, because the post-commit scheduler has a broader vision of the code. For instance, while ReLaSch can schedule together two independent instructions that are distant in the code, a conventional out-oforder processor only issues them in the same cycle if both are in-flight. The ReLaSch processor predicts the branch targets, memory aliases and latencies at scheduling time, out of the critical path. The prediction is based on the most recent executions at scheduling time. Furthermore, most of the register renaming process is performed by the scheduler and is removed from the execution pipeline. Our experiments show that ReLaSch has the same average IPC as our reference out-of-order processor and is clearly better than the reference inorder processor (1.55 speed-up). In all cases it outperforms the in-order processor and in 23 benchmarks out of 40 it has a higher IPC than the reference out-of-order processor.

With the improvement in VLSI technology, realization of multiple processor cores on a single chip becomes easier. Therefore, more and more users execute applications on current multi-core architectures. The multi-core system has a brilliant performance in executing multi-threaded applications, but this system could not gain any performance in single-threaded applications. This paper proposes a multi-core architecture for enhancing single-threaded performance in embedded system, and focuses on four points: 1. Construct a simple out-of-order execution core. 2. Design a dynamically scheduled instruction analyzer. 3. Design a mechanism for sharing operands between two cores. 4. Design a mechanism for committing instructions synchronously between two cores. The architecture of each core is single-issue out-of-order instruction pipe. First, instruction analyzer will fetch instructions and generate instruction dependence tags by detecting the dependencies among the fetched instructions, then schedule instructions dynamically and dispatch to the cores. In the core, instructions can know where to get required operands according to the information of instruction tags, this mechanism enables data can be shared between two cores. Instructions are executed by data-driven approach, but in-order complete to maintain the correctness of the program order. Based on ARM instruction set, this paper tries to explore ways to achieve interaction control mechanisms between two cores and to accelerate a single-thread in the dual-core architecture. We write a simulation model of the proposed architecture in C language as our trace-driven simulation framework and the MediaBench suite is selected for the experiments. According simulation result, the architecture can obtain average 40% performance speedup comparing to the five-stage pipelined architecture.

ISA extensions are a very powerful approach to implement new hardware techniques that require or benefit from compiler support: decisions made at compile time can be complemented at runtime, achieving a synergistic effect between the compiler and the processor. This thesis is focused on two ISA extensions: predicate execution and register windows. Predicate execution is exploited by the if-conversion compiler technique. If-conversion removes control dependences by transforming them to data dependences, which helps to exploit ILP beyond a single basic-block. Register windows help to reduce the amount of loads and stores required to save and restore registers across procedure calls by storing multiple contexts into a large architectural register file.In-order processors specially benefit from using both ISA extensions to overcome the limitations that control dependences and memory hierarchy impose on static scheduling. Predicate execution allows to move control dependence instructions past branches. Register windows reduce the amount of memory operations across procedure calls. Although if-conversion and register windows techniques have not been exclusively developed for in-order processors, their use for out-of-order processors has been studied very little. In this thesis we show that the uses of if-conversion and register windows introduce new performance opportunities and new challenges to face in out-of-order processors.The use of if-conversion in out-of-order processors helps to eliminate hard-to-predict branches, alleviating the severe performance penalties caused by branch mispredictions. However, the removal of some conditional branches by if-conversion may adversely affect the predictability of the remaining branches, because it may reduce the amount of correlation information available to the branch predictor. Moreover, predicate execution in out-of-order processors has to deal with two performance issues. First, multiple definitions of the same logical register can be merged into a single control flow, where each definition is guarded with a different predicate. Second, instructions whose guarding predicate evaluates to false consume unnecessary resources. This thesis proposes a branch prediction scheme based on predicate prediction that solves the three problems mentioned above. This scheme, which is built on top of a predicated ISA that implement a compare-and-branch model such as the one considered in this thesis, has two advantages: First, the branch accuracy is improved because the correlation information is not lost after if-conversion and the mechanism we propose permits using the computed value of the branch predicate when available, achieving 100% of accuracy. Second it avoids the predicate out-of-order execution problems.Regarding register windows, we propose a mechanism that reduces physical register requirements of an out-of-order processor to the bare minimum with almost no performance loss. The mechanism is based on identifying which architectural registers are in use by current in-flight instructions. The registers which are not in use, i.e. there is no in-flight instruction that references them, can be early released.In this thesis we propose a very efficient and low-cost hardware implementation of predicate execution and register windows that provide important benefits to out-of-order processors.

Bereavement is painful at any time of life. For young children experiencing bereavement, grandmothers are often the first line of defense. Grandmothers are frequently called upon when their family members experience an out-of-order death, and while they are willing to provide care, grandmothers don't always know the best way forward. This qualitative study sought to learn more about the grief experiences of 22 grandmothers who had lost a family member prematurely through semi-structured interviews and Interpretive Phenomenological Analysis. Findings suggest (a) grandmothers experience layered grief in that they grieve the loss of the family member, experience the pain of the surviving family members, and their own pain; (b) grandmothers experience invisible grief as their feelings are not often revealed to or recognized by their family members; (c) grandmothers experience confusion in knowing how to help and attend to their family members who are bereaved. These difficulties seem related to the family relationships, the connection to the person who died (their own child or an in-law child or grandchild), what they are grieving, and their ability to develop new roles and relationships during the bereavement period.

Η σχεδίαση μικροεπεξεργαστών είναι μια πολύπλοκη και σύνθετη διαδικασία, η οποία δυσκολεύει όσο οι τεχνολογικές εξελίξεις προχωράνε. Οι μελετητές της απόδοσης των μικροεπεξεργαστών, για να μελετήσουν την απόδοση ενός συστήματος καταλήγουν στη χρησιμοποίηση πλήρους προσομοίωσης, καάτι που είναι εξαιρετικά πολύπλοκο και χρονοβόρο. Σε αυτή την εργασία παρουσιάζεται ένα αναλυτικό μοντέλο που μοντελοποιεί τις επιδόσεις του επεξεργαστή με βάση το πρόγραμμα που εκτελεί και τα δομικά του χαρακτηριστικά. Το μοντέλο αυτό βασίζεται πάνω σε έναν εκτός σειράς υπερβαθμωτό επεξεργαστή. Η μοντελοποίηση βασίζεται στο γεγονός ότι ένας υπερβαθμωτός επεξεργαστής ο οποίος είναι ισορροπημένος διατηρεί σταθερή την απόδοση του εκτός αν συναντήσει ανασχετικά γεγονότα, όπως αποτυχία πρόσβασης στην κρυφή μνήμη ή λάθος στην πρόβλεψη διακλάδωσης. Τα δεδομένα του προγράμματος συλλέγονται κατά την εκτέλεση του προγράμματος με τη χρήση ενός εργαλείου παρεμβολής κώδικα σε εκτελέσιμο αρχείο, το οποίο ονομάζεται DIOTA. Παρουσιάζεται το μοντέλο σταθερής απόδοσης και μετριέται ο αντίκτυπος του κάθε ανασχετικού γεγονότος ξεχωριστά. / Microprocessor design is a complex and difficult process which day by day is getting more difficult as technology advances. Designers, in order to study the efficiency of a microprocessor tend to use full cycle simulation, which is extremely complex and time-consuming. In this thesis, an analytical model is presented, which is modelling the perfonmance of a proccessor in account with the executable and processor's functional characteristics. The model is based on an out of order superscalar processor. The modelling is based on the fact that a balanced superscalar processor is maintaining a steady performance rate, unless a disruptive miss event happens, such as a data cache miss or a branch misprediction. The data from the executable are gathered by using a binary rewriting tool, called DIOTA. The steady state model is being presented, and the impact of each miss event is measured.

The demand for high-speed networking applications has made Network Processors (NPs) and Central Computing Units (CPUs) increasingly parallel and complex, containing numerous on-chip processing cores. This parallelism can only be exploited fully by the underlying packet scheduler by efficiently utilizing all the available cores. Classically, packets have been directed towards the processing cores at flow granularity, making them susceptible to traffic locality. Ensuring a good load balance among the processors improves the application’s throughput and packet loss characteristics. Hence, packet-level schedulers dispatch flows to the processing core at a packet granularity to improve the load balance. However, packet-level scheduling combined with advanced parallelism introduces out-of-order departure of the processed packets. Simultaneously optimizing both the load balance and packet order is challenging. In this degree project, we micro-benchmark the DPDK’s (Dataplane Development Kit) event scheduler and identify many performance and scalability bottlenecks. We find the event scheduler consumes around 40% of the cycles on each participating core for event scheduling. Additionally, we find that DSW (Distributed Software Scheduler) cannot saturate all the workers with traffic because a single NIC (Network Interface Card) queue is polled for packets in our test setup. Then we propose Diffuser, an event scheduler for DPDK that combines the functional properties of both the flow and packet-level schedulers. The diffuser aims to achieve optimal load balance while minimizing out-of-order packet transmission. Diffuser uses stochastic flow assignments along with a load imbalance feedback mechanism to adaptively control the rate of flow migrations to optimize the scheduler’s load distribution. Diffuser reduces packet reordering by at least 65% with ten flows of 100 bytes at 25 MPPS (Million Packet Per Second) and at least 50% with one flow. While Diffuser improves the reordering performance, it slightly reduces throughput and increases latency due to flow migrations and reduced cache locality / Efterfrågan på höghastighets-nätverksapplikationer har gjort nätverkspro-cessorer (NP) och centrala beräkningsenheter (CPU:er) alltmer parallella, komplexa och innehållande många processorkärnor. Denna parallellitet kan endast utnyttjas fullt ut av den underliggande paketschemaläggaren genom att effektivt utnyttja alla tillgängliga kärnor. Vanligtvis har paketschemaläggaren skickat paket till olika kärnor baserat på flödesgranularitet, vilket medför trafik-lokalitet. En bra belastningsbalans mellan processorerna förbättrar applikationens genomströmning och minskar förlorade paket. Därför skickar schemaläggare på paketnivå istället flöden till kärnan med en paketgranularitet för att förbättra lastbalansen. Schemaläggning på paketnivå kombinerat med avancerad parallellism innebär dock att de behandlade paketen avgår i oordning. Att samtidigt optimera både lastbalans och paketordning är en utmaning. I detta examensprojekt utvärderar vi DPDKs (Dataplane Development Kit) händelseschemaläggare och hittar många flaskhalsar i prestanda och skalbarhet. Vi finner att händelseschemaläggaren konsume-rar cirka 40 % av cyklerna på varje kärna.Dessutom finner vi att DSW (Schemaläggare för distribuerad programvara) inte kan mätta alla arbetande kärnor med trafik eftersom en enda nätverkskorts-kö används i vår testmiljö. Vi introducerar också Diffuser, en händelse-schemaläggare för DPDK som kombinerar egenskaperna hos både flödes-och paketnivåschemaläggare. Diffuser ämnar att uppnå optimal lastbalans samtidigt som den minimerar paketöverföring i oordning. Den använder stokastiska flödestilldelningar tillsammans med en återkopplingsmekanism för lastobalans för att adaptivt kontrollera flödesmigreringar för att optimera lastfördelningen. Diffuser minskar omordning av paket med minst 65 % med tio flöden på 100 byte vid 25 MPPS (Miljoner paket per sekund) och minst 50 % med endast ett flöde. Även om Diffuser förbättrar omordningsprestandan, minskar den genomströmningen något och ökar latensen på grund av flödesmigreringar och minskad cache-lokalitet.

Los procesadores superescalares actuales utilizan un reorder buffer (ROB) para contabilizar las instrucciones en vuelo. El ROB se implementa como una cola FIFO first in first out en la que las instrucciones se insertan en orden de programa después de ser decodificadas, y de la que se extraen también en orden de programa en la etapa commit. El uso de esta estructura proporciona un soporte simple para la especulación, las excepciones precisas y la reclamación de registros. Sin embargo, el hecho de retirar instrucciones en orden puede degradar las prestaciones si una operación de alta latencia está bloqueando la cabecera del ROB. Varias propuestas se han publicado atacando este problema. La mayoría utiliza retirada de instrucciones fuera de orden de forma especulativa, requiriendo almacenar puntos de recuperación (checkpoints) para restaurar un estado válido del procesador ante un fallo de especulación. Normalmente, los checkpoints necesitan implementarse con estructuras hardware costosas, y además requieren un crecimiento de otras estructuras del procesador, lo cual a su vez puede impactar en el tiempo de ciclo de reloj. Este problema afecta a muchos tipos de procesadores actuales, independientemente del número de hilos hardware (threads) y del número de núcleos de cómputo (cores) que incluyan. Esta tesis abarca el estudio de la retirada no especulativa de instrucciones fuera de orden en procesadores superescalares, multithread y multicore. / Ubal Tena, R. (2010). Out-of-Order Retirement of Instructions in Superscalar, Multithreaded, and Multicore Processors [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8535

Bien que les processeurs actuels possèdent plus de 10 cœurs, de nombreux programmes restent purement séquentiels. Cela peut être dû à l'algorithme que le programme met en œuvre, au programme étant vieux et ayant été écrit durant l'ère des uni-processeurs, ou simplement à des contraintes temporelles, car écrire du code parallèle est notoirement long et difficile. De plus, même pour les programmes parallèles, la performance de la partie séquentielle de ces programmes devient rapidement le facteur limitant l'augmentation de la performance apportée par l'augmentation du nombre de cœurs disponibles, ce qui est exprimé par la loi d'Amdahl. Conséquemment, augmenter la performance séquentielle reste une approche valide même à l'ère des multi-cœurs.Malheureusement, la façon conventionnelle d'améliorer la performance (augmenter la taille de la fenêtre d'instructions) contribue à l'augmentation de la complexité et de la consommation du processeur. Dans ces travaux, nous revisitons une technique visant à améliorer la performance de façon orthogonale : La prédiction de valeurs. Au lieu d'augmenter les capacités du moteur d'exécution, la prédiction de valeurs améliore l'utilisation des ressources existantes en augmentant le parallélisme d'instructions disponible.En particulier, nous nous attaquons aux trois problèmes majeurs empêchant la prédiction de valeurs d'être mise en œuvre dans les processeurs modernes. Premièrement, nous proposons de déplacer la validation des prédictions depuis le moteur d'exécution vers l'étage de retirement des instructions. Deuxièmement, nous proposons un nouveau modèle d'exécution qui exécute certaines instructions dans l'ordre soit avant soit après le moteur d'exécution dans le désordre. Cela réduit la pression exercée sur ledit moteur et permet de réduire ses capacités. De cette manière, le nombre de ports requis sur le fichier de registre et la complexité générale diminuent. Troisièmement, nous présentons un mécanisme de prédiction imitant le mécanisme de récupération des instructions : La prédiction par blocs. Cela permet de prédire plusieurs instructions par cycle tout en effectuant une unique lecture dans le prédicteur. Ces trois propositions forment une mise en œuvre possible de la prédiction de valeurs qui est réaliste mais néanmoins performante. / Although currently available general purpose microprocessors feature more than 10 cores, many programs remain mostly sequential. This can either be due to an inherent property of the algorithm used by the program, to the program being old and written during the uni-processor era, or simply to time to market constraints, as writing and validating parallel code is known to be hard. Moreover, even for parallel programs, the performance of the sequential part quickly becomes the limiting improvement factor as more cores are made available to the application, as expressed by Amdahl's Law. Consequently, increasing sequential performance remains a valid approach in the multi-core era. Unfortunately, conventional means to do so - increasing the out-of-order window size and issue width - are major contributors to the complexity and power consumption of the chip. In this thesis, we revisit a previously proposed technique that aimed to improve performance in an orthogonal fashion: Value Prediction (VP). Instead of increasing the execution engine aggressiveness, VP improves the utilization of existing resources by increasing the available Instruction Level Parallelism. In particular, we address the three main issues preventing VP from being implemented. First, we propose to remove validation and recovery from the execution engine, and do it in-order at Commit. Second, we propose a new execution model that executes some instructions in-order either before or after the out-of-order engine. This reduces pressure on said engine and allows to reduce its aggressiveness. As a result, port requirement on the Physical Register File and overall complexity decrease. Third, we propose a prediction scheme that mimics the instruction fetch scheme: Block Based Prediction. This allows predicting several instructions per cycle with a single read, hence a single port on the predictor array. This three propositions form a possible implementation of Value Prediction that is both realistic and efficient.

La complexité des CPUs s’est accrue considérablement depuis leurs débuts, introduisant des mécanismes comme le renommage de registres, l’exécution dans le désordre, la vectorisation, les préfetchers et les environnements multi-coeurs pour améliorer les performances avec chaque nouvelle génération de processeurs. Cependant, la difficulté a suivi la même tendance pour ce qui est a) d’utiliser ces mêmes mécanismes à leur plein potentiel, b) d’évaluer si un programme utilise une machine correctement, ou c) de savoir si le design d’un processeur répond bien aux besoins des utilisateurs.Cette thèse porte sur l’amélioration de l’observabilité des facteurs limitants dans les boucles de calcul intensif, ainsi que leurs interactions au sein de microarchitectures modernes.Nous introduirons d’abord un framework combinant CQA et DECAN (des outils d’analyse respectivement statique et dynamique) pour obtenir des métriques détaillées de performance sur des petits codelets et dans divers scénarios d’exécution.Nous présenterons ensuite PAMDA, une méthodologie d’analyse de performance tirant partie de l’analyse de codelets pour détecter d’éventuels problèmes de performance dans des applications de calcul à haute performance et en guider la résolution.Un travail permettant au modèle linéaire Cape de couvrir la microarchitecture Sandy Bridge de façon détaillée sera décrit, lui donnant plus de flexibilité pour effectuer du codesign matériel / logiciel. Il sera mis en pratique dans VP3, un outil évaluant les gains de performance atteignables en vectorisant des boucles.Nous décrirons finalement UFS, une approche combinant analyse statique et simulation au cycle près pour permettre l’estimation rapide du temps d’exécution d’une boucle en prenant en compte certaines des limites de l’exécution en désordre dans des microarchitectures modernes / The complexity of CPUs has increased considerably since their beginnings, introducing mechanisms such as register renaming, out-of-order execution, vectorization,prefetchers and multi-core environments to keep performance rising with each product generation. However, so has the difficulty in making proper use of all these mechanisms, or even evaluating whether one’s program makes good use of a machine,whether users’ needs match a CPU’s design, or, for CPU architects, knowing how each feature really affects customers.This thesis focuses on increasing the observability of potential bottlenecks inHPC computational loops and how they relate to each other in modern microarchitectures.We will first introduce a framework combining CQA and DECAN (respectively static and dynamic analysis tools) to get detailed performance metrics on smallcodelets in various execution scenarios.We will then present PAMDA, a performance analysis methodology leveraging elements obtained from codelet analysis to detect potential performance problems in HPC applications and help resolve them. A work extending the Cape linear model to better cover Sandy Bridge and give it more flexibility for HW/SW codesign purposes will also be described. It will bedirectly used in VP3, a tool evaluating the performance gains vectorizing loops could provide.Finally, we will describe UFS, an approach combining static analysis and cycle accurate simulation to very quickly estimate a loop’s execution time while accounting for out-of-order limitations in modern CPUs