1,720,995 research outputs found
Asynchronous dynamic graph processing with real-time analysis
No full textThe rapid increase in connected data from various sources such as the World Wide Web, social networks, and financial transactions has led to the widespread use of graph-based representations for data analysis of these networks. However, traditional high-performance computing (HPC) solutions designed for static graphs are inefficient and impractical for dynamic graphs that evolve over time. This approach leads to high overheads, loss of information between snapshots, and potential correctness issues.
The demand for fast, real-time analytics on continuously evolving real-world systems at a massive scale has become critical for applications such as online recommendations, financial fraud detection, and counter-terrorism. For example, social media networks like Facebook handle potentially millions of interactions per second, and payment networks like Visa process thousands of transactions per second. To address these challenges, my dissertation focuses on the opportunities and challenges of analyzing dynamic graphs in real-time, offering an infrastructure-algorithm co-design for dynamic graph analytics at scale.
To this end, I develop and present a pattern for dynamic graph algorithms, and a supporting software infrastructure architecture, that together form a cohesive real-time graph analysis model. My algorithm pattern is designed to be amenable to distributed systems with concepts such as message passing, asynchronicity, and termination, while considering the timeliness requirements for real-time analysis. The infrastructure architecture considers real-world properties of dynamic data generation and hardware constraints, aiming for versatility, performance, and scalability. It supports dynamic graph topology evolution and provides interfaces for expressing algorithms for dynamic graph analysis and collecting results during runtime.
I demonstrate that many common static graph algorithms can be re-designed for dynamic processing and real-time analysis, and can be built and scaled efficiently. My dynamic graph model offers advantages over static designs, such as low-cost updates to the graph and the ability to observe algorithm results before or after topology modifications. The implementation of my model shows near-linear scalability in performance, and supports real-time analysis at potentially orders of magnitude higher evolution rates compared to alternative designs; providing a generic, scalable, and performant solution for dynamic graph analysis, addressing the challenges of analyzing large-scale, continuously evolving network data in real-time.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
On paradigm shifts : enabling proactive defenses by identifying the vulnerable population, and online bitemporal dynamic graph analytics
No full textFueled by the massive amount of data and meta-data harvested by large-scale online service providers, two trends stand out: the broad adoption of machine learning particularly for cybersecurity defenses, and the growing pains of temporal graph analytics particularly for dynamically evolving systems.
In this dissertation, my overarching goal is to explore novel ways: to effectively harness this harvested data to evidently improve the security of online platforms in general and their most vulnerable users in particular, and to explicitly model the temporal evolution of this data to efficiently enable business use cases that can not be served by existing graph analytics systems. To that end, I advocate for a paradigm shift across two high impact domains: cybersecurity and graph analytics.
On the one hand, existing cybersecurity defenses are reactive, and victim-agnostic: they are predicated on identifying the attacks/attackers, and do not take user characteristics into account. In contrast, I propose a proactive approach based on identifying the vulnerable population, and leveraging this information to improve the security of the platform in general and the most vulnerable users in particular.
To that end, I approach harnessing the vulnerable population under a victim-centric defense paradigm while contrasting against conventional defenses, and demonstrate its feasibility using four months of production data encompassing billions of events from hundreds of millions of users.
To my knowledge, I am the first to propose and discuss such a defense paradigm.
On the other hand, existing graph analytics systems are mostly static, and non-temporal: they are not fully able to support modeling systems that evolve dynamically over time while supporting the queries (including current state, historical, and audit queries) required by today's use cases. In contrast, I contend that future graph analytics systems should be: online, dynamic, and employ bitemporal modeling at their core.
To that end, I examine the use cases that are an ideal match for an online bitemporal dynamic graph analytics system, explore the design trade-off space, and develop and characterize several designs targeting different points within that space.
To my knowledge, I am the first to propose, develop, and characterize such a system end-to-end.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
Towards variability-aware frequency scaling on heterogeneous edge platforms
No full textRecent Edge applications (e.g., machine learning inference) are becoming more sophisticated and computationally demanding. To meet their Quality of Service (QoS) objectives, today’s heterogeneous Edge platforms (e.g., NVIDIA Jetson platform) incorporate several architectural innovations. One that stands out is the wide frequency configuration space (more than a dozen frequency levels per processing unit spanning a 10x max-min ratio). We postulate that this can be harnessed to better navigate the trade-off space between performance and power consumption.
This dissertation makes progress towards harnessing frequency scaling on Edge platforms. We start by exploring the potential gains from frequency scaling on the NVIDIA Jetson platform. To this end, we develop an empirical methodology to characterize the performance and power consumption behavior of the Jetson platform under different frequency configurations. Our characterization indicates that indeed there is an opportunity to improve performance and/or energy-efficiency with careful frequency configuration selection. However, one challenge is to estimate the impact of the frequency configuration choice on performance and power consumption of the workload.
To overcome this challenge, we employ machine learning techniques to build performance and power consumption models for the target workload. While developing these models, we find that the quality of their predictions depends on where the models are deployed (even if they are deployed on identical devices with identical software stacks). This leads us to postulate that variability in performance and power consumption among nominally identical Edge platforms exists and is sizeable. To investigate this hypothesis, we develop statistical tools that allow developers to detect, quantify, categorize, and compare variability. Then we present a set of actions one can take to mitigate the impact of variability. We evaluate all the techniques and approaches on two clusters of popular Edge platforms - the Jetson AGX and Nano.
Finally, we focus on developing variability-aware performance and power
consumption models. We show that not accounting for variability can severely impact the quality of predictions. The evaluation of the models shows that accounting for inter-node variability improves the Root Mean Square Error (RMSE) by 9.5% and 31.9% for runtime and power models respectively.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
EdgeEngine : a thermal-aware optimization framework for edge inference
No full textHeterogeneous edge platforms enable the efficient execution of machine learning inference applications. These applications often have a critical constraint (such as meeting a deadline) and an optimization goal (such as minimizing energy consumption). To navigate this space, existing optimization frameworks adjust the platform's frequency configuration for the CPU, the GPU and/or the memory controller. These optimization frameworks, however, are thermal-oblivious disregarding the fact that edge platforms are frequently deployed in environments where they are exposed to ambient temperature variations.
In this thesis, we first characterize the impact of ambient temperature on the power consumption and execution time of machine learning inference applications running on a popular edge platform, the NVIDIA Jetson TX2. Our rigorous data collection and statistical methodology reveals a sizeable ambient temperature impact on power consumption (about 20\% on average, and up to 40\% on some workloads) and a moderate impact on runtime (up to 5\%). We also find that existing, thermal-oblivious optimization frameworks select frequency configurations that either violate the application's constraints and/or are sub-optimal in terms of the optimization goal assigned.
To address these shortcomings, we propose EdgeEngine, a lightweight thermal-aware optimization framework. EdgeEngine monitors the platform's temperature and uses reinforcement learning to adjust the frequency configuration of all underlying platform resources to meet the application's constraints. We find that EdgeEngine meets the application's constraint, and achieves up to 29\% lower energy consumption (up to 2x) and up to 41\% fewer violations compared to existing state-of-the-art thermal-oblivious optimization frameworks.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
PiMPACT : (re)assessing PiM impact
No full textProcessing-in-Memory (PiM) has gained attention as a potential solution to address the "memory wall" in high-performance computing applications. Recently the first general-purpose PiM technology - dubbed UPMEM - has been made commercially available.
While several studies report substantial advantage (often as application speedup) of UPMEM-equipped servers over high-end CPUs, these findings are often "fragile" due to overlooked factors, such as: (i) using unoptimized code on either one or both sides of the comparison, (ii) excluding overheads inherent to the accelerator-like processing model offered by UPMEM, (iii) ignoring power or energy consumption in the comparison, and (iv) high dependence on the the choice of CPU hardware baseline which can dramatically change the conclusions. This thesis aims to address these limitations by reexamining UPMEM PiM’s effectiveness within specific
application contexts.
To that end, we focus on applications that are well-suited for UPMEM, primarily in the area of genomic sequence alignment, and conduct a rigorous performance evaluation, ensuring both UPMEM and CPU codes are reasonably optimized, extending the comparison to include power consumption, and performing cost- and power-normalized comparisons to mitigate hardware dependency.
Our experiments reveal that, after applying optimizations to CPU baselines, the previously observed performance gap narrows significantly, and in many cases, the CPU-equipped servers offer an advantage even in terms of raw performance. More importantly, cost- and power-normalized comparisons suggest that while UPMEM may offer potential benefits in the future, the current technology is unlikely to offer a cost- or power-normalized advantage compared to CPU baselines for the set of applications we evaluate.
Finally, we provide practical heuristics to guide decisions on which types of computational tasks are best suited for offloading to UPMEM PiM system. These insights aim to assist researchers and practitioners in effectively leveraging UPMEM technology where may offer an advantage.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
Two problems in dynamic graph analytics : maximum flow and online partitioning
No full textMany real-world systems, such as social networks and financial transactions, evolve quickly over time and can be modelled as dynamic graphs. Dynamic graph processing systems emerged to provide timely analysis on these graphs, ingesting graph updates through one or more streams, and providing (on-demand or regularly) answers to a standing query. This thesis explores both the algorithmic and the infrastructural aspects of dynamic graph processing.
On the algorithm side, this thesis proposes the vertex-local invariant restoration approach for designing dynamic graph algorithms. With this approach, we propose a novel algorithm for the maximum flow problem, targeting graphs that evolve quickly with millions of edge changes per second. The algorithm works well on a shared-nothing, asynchronous computational model in which the graph topology is updated concurrently as the algorithm executes. We prove that the algorithm is correct and provide a thorough experimental evaluation with difficult cases on large real-world dynamic graphs, showing that the algorithm obtains high throughputs, supports both additions and deletions efficiently, and provides results with low latency and high stability.
On the infrastructure side, this thesis explores a new problem that appears when processing dynamic graphs: online partitioning. A common model in dynamic graph processing is that the system ingests a stream of edge updates (edge add/remove/modify events), and creates and assigns a vertex—and its edge list—to a partition when first observing an edge that references the vertex. The common solution is to use random partitioning—vertices assigned to partitions based on hashes of their IDs, but it leads to suboptimal edge-cut minimization and/or load balance. This thesis proposes the Minimum Load with Affinity framework for systematic exploration of the trade-offs in a partitioning strategy: load balance, edge-cut minimization, and ingestion delay. The preliminary results show that MLA can (i) achieve a 7%-14% reduction in edge-cuts without sacrificing load balance (or a much higher reduction by sacrificing load balance), and (ii) achieve both better edge-cut minimization and load balance by ingesting edges in batches and reasoning about batch properties (at the cost of higher ingestion latency).Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
