Due to the progress of Internet technology and technical improvement, the growths of multimedia products and services ,such as Multimedia Message Service¡]MMS¡^, Multimedia on Demand¡]MoD¡^, Video Conferencing, and Digital TV, are very fast. All of these services need good video compression and audio compression standards to support. It is impossible to transmit source data of multimedia on networks. Motion Estimation needs the most computing complexity in the video compression. In our research, we focus on how to reduce candidate blocks and keep video quality. We study some fast motion estimation algorithms and architectures, and design a fast motion estimation architecture which supports resolution of 1280x720 at 30fps frame rate in HDTV specification based on hierarchical motion estimation algorithm. In the limit of hardware resources and the compressed video quality, the architecture can improve inter-coding performance. Two adjacent MacroBlocks have similar Motion Vector in our observation. We arrange a 16x8 processing element array to deal with two adjacent MacroBlocks together. The design can reduce a lot of clock cycles in the hierarchical motion estimation architecture, and keep high video quality. Furthermore, we propose a search range prediction method¡]called ASR¡^which reflect the motion behavior of video sequences into search range on MB-By-MB Basis. ASR can reduce the unnecessary operation of candidate blocks and keep very high video quality compared with Full Search Block Matching algorithm by the implementation in official software of the new video compression standard, Joint Model of H.264/AVC.

The most basic requirement for any computer controlled game agent in a video game is to be able to successfully navigate the game environment. Pathfinding is an essential component of any agent navigation system. Pathfinding is, at the simplest level, a search technique for finding a route between two points in an environment. The real-time multi-agent nature of video games places extremely tight constraints on the pathfinding problem. This study aims to provide the first complete review of the current state of video game pathfinding both in regards to the graph search algorithms employed as well as the implications of pathfinding within dynamic game environments. Furthermore this thesis presents novel work in the form of a domain specific search algorithm for use on grid-based game maps: the spatial grid A* algorithm which is shown to offer significant improvements over A* within the intended domain. Copyright / Dissertation (MSc)--University of Pretoria, 2011. / Computer Science / unrestricted

The strategy game Risk is a very popular boardgame, requiring little effort to learn but lots of skill to master.The aim of this project is to explore the fortification phase of thegame, where the player’s troops are moved between territories.Our method is based on adapting Monte Carlo tree search(MCTS) to Risk. To improve the troop movements, we proposetwo techniques, hierarchical search and progressive bias. Thesemethods, combined with other extensions of MCTS are thencompared against a baseline player of the game. Our results showthat hierarchical search improved the MCTS agent’s playingpower and the progressive bias have potential to improve theagent but needs further investigation. / Strategispelet Risk är ett väldigt populärt brädspel som är lätt att lära sig men svårt att bemästra. Syftet med detta projekt är att utforska spelets befästningsfas, där spelarens trupper flyttas mellan territorier. Vår metod är baserad på en anpassning av Monte Carlo trädsökning (MCTS) till Risk. För att förbättra trupprörelserna föreslår vi två tekniker, ”hierarchical search” och ”progressive bias”. Dessa metoder, i kombination med andra tillägg av MCTS, jämförs sedan mot en standard agent i spelet. Våra resultat visar att hierarchical search förbättrade MCTS agentens spelstyrka och att progressivce bias har möjlighet att förbättra agenten men kräver fortsatt utforskning. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

<p dir="ltr">Specialized hardware accelerators are becoming increasingly common to provide application performance gain despite the slowing trend of transistor scaling. Accelerators can adapt to the compute and data dependency patterns of an application to fully exploit the parallelism of the application and reduce data movement. However, specialized hardware is often limited by the application it was tailored to, which can lead to idle or inactive silicon in computations that do not match the exact patterns it was designed for. In this work I study two cases of GPU specialization and techniques that can be used to improve performance in a broader domain of applications. </p><p dir="ltr">First, I examine the effects of GPU core partitioning, a trend in contemporary GPUs to sub-divide core components to reduce area and energy overheads. Core partitioning is essentially a specialization of the hardware towards balanced applications, wherein the intra-core connectivity provides minimal benefit but takes up valuable on-chip area. I identify four orthogonal performance effects of GPU core sub-division, two of which have significant impact in practice: a bottleneck in the read operand stage caused by the reduced number of collector units and register banks allocated to each sub-core, and an instruction issue imbalance across sub-core schedulers caused by a simple round robin assignment of threads to sub-cores. To alleviate these issues I propose a Register Bank Aware (RBA) warp scheduler, which uses feedback from current register bank contention to inform thread scheduling decisions, and a hashed sub-core work scheduler to prevent pathological issue imbalances caused by round robin scheduling. I rigorously evaluate these designs in simulation and show they are able to capture 81% of the performance lost due to core subdivision. Further, I evaluate my techniques using synthesis tools and find that RBA is able to achieve performance equivalent to doubling the number of operand Collector Units (CUs) per sub-core with only a 1% increase in area and power.</p><p dir="ltr">Second, I study the inclusion of specialized ray tracing accelerator cores on GPUs. Specialized ray-tracing acceleration units have become a common feature in GPU hardware, enabling real-time ray-tracing of complex scenes for the first time. The ray-tracing unit accelerates the traversal of a hierarchical tree data structure called a bounding volume hierarchy to determine whether rays have intersected triangle primitives. Hierarchical search algorithms are a fundamental software pattern common in many important domains, such as recommendation systems and point cloud registration, but are difficult for GPUs to accelerate because they are characterized by extensive branching and recursion. The ray-tracing unit overcomes these limitations with specialized hardware to traverse hierarchical data structures efficiently, but is mired by a highly specialized graphics API, which is not readily adaptable to general-purpose computation. In this work I present the Hierarchical Search Unit (HSU), a flexible datapath to accelerate a more general class of hierarchical search algorithms, of which ray-tracing is one. I synthesize a baseline ray-intersection datapath and maximize functional unit reuse while extending the ray-tracing unit to support additional computations and a more general set of instructions. I demonstrate that the unit can improve the performance of three hierarchical search data structures in approximate nearest neighbors search algorithms and a B-tree key-value store index. For a minimal extension to the existing unit, HSU improves the state-of-the-art GPU approximate nearest neighbor implementation by an average of 24.8% using the GPU's general computing interface.</p>