Browsing by Author "Kawash, Jalal"
Results Per Page
Sort Options
Item Open Access BOUNDS FOR MUTUAL EXCLUSION WITH ONLY PROCESSOR CONSISTENCY(1999-12-15) Higham, Lisa; Kawash, JalalMost weak memory consistency models are incapable of supporting a solution to mutual exclusion using only read and write operations. Processor Consistency-Goodman's version is an exception. Ahamad et al.[1] showed that Peterson's mutual exclusion algorithm is correct for PC-G, but Lamport's bakery algorithm is not. In this paper, we derive a lower bound on the number and type (single- or multi-writer) of variables that a mutual exclusion algorithm must use in order to be correct for PC-G. We show that any such solution for n processes must use at least one multi-writer and n single-writers. This lower bound is tight when n = 2, and is tight when n >_2 for solutions that do not provide fairness. We show that Burn's algorithm is an unfair solution for mutual exclusion in PC-G that achieves our bound. However, five other known algorithms that use the same number and type of variables are incorrect for PC-G. A corollary of this investigation is that, in contrast to Sequential Consistency, multi-writers cannot be implemented from single-writers in PC-G.Item Open Access Capturing Register and Control Dependence in Memory Consistency Models with Applications to the Itanium Architecture(2006-07-11) Higham, Lisa; Jackson, LillAnne; Kawash, JalalA complete framework for modelling memory consistency that includes register and control dependencies is presented. It allows us to determine whether or not a given computation could have arisen from a given program running on a given multiprocessor architecture. The framework is used to provide an exact description of the computations of (a subset of) the Itanium instruction set on an Itanium multiprocessor architecture. We show that capturing register and control dependencies is crucial: a producer/consumer problem is solvable without using strong synchronization primitives on Itanium multiprocessors, but is impossible without exploiting these dependencies. Keywords: Multiprocessor Memory consistency, register and control dependency, Itanium, process coordination.Item Open Access Characterizing D2L Usage at the U of C(2017) Roy, Sourish; Williamson, Carey; Wang, Mea; Williamson, Carey; Kawash, JalalOver the last decade, online Learning Management System (LMS) services have been utilized by many universities. Desire2Learn (D2L) is the official LMS used by the University of Calgary (U of C). Every student, teaching assistant, and faculty member has access to D2L services. This thesis presents a workload characterization study of the D2L Web site for on-campus and off-campus users based on a period of two calender years, 2015 and 2016. D2L mainly provides online learning services, delivers course content, and monitors student progress. It uses content delivery networks consisting of geographically dispersed nodes. Persistent and parallel connections are used extensively throughout D2L sessions with users. This thesis sheds light upon the usage of modern LMS services like D2L. It utilizes network-level data for an extended period of time. Our measurement results highlight the impacts of network latency on the user-perceived D2L performance at the U of C.Item Open Access CRITICAL SECTIONS AND PRODUCER/CONSUMER QUEUES IN WEAK MEMORY SYSTEMS(1997-06-01) Higham, Lisa; Kawash, JalalIn machines with a weak memory consistency model, the ordering constraints on memory accesses are few. In order to properly program these machines, certain powerful or explicit synchronization instructions are additionally provided in their architecture. We show that although a solution to the critical section problem (also referred to as the mutual exclusion problem) is impossible without such powerful synchronization, certain versions of the producer/consumer problem can be solved even in the weakest systems without the need for any such powerful instructions. These instructions are expensive, and avoiding their use is desirable for better performance.Item Open Access Data Structures, Algorithms and Applications for Big Data Analytics: Single, Multiple and All Repeated Patterns Detection in Discrete Sequences(2017) Xylogiannopoulos, Konstantinos; Alhajj, Reda; Rokne, Jon; Pardalos, Panayote; Kawash, Jalal; Helaoui, MohamedMy research work of the current thesis focuses on the detection of single, multiple and all repeated patterns in sequences. Many algorithms exist for single pattern detection that take an input argument (i.e., pattern to be detected) and produce as outcome the position(s) where the pattern exists. However, to the best of my knowledge, there is nothing in literature related to all repeated patterns detection, i.e., the detection of every pattern that occurs at least twice in one or more sequences. This is a very important problem in science because the outcome can be used for various practical applications, e.g., forecasting purposes in weather analysis or finance by detecting patterns having periodicity. The main problem of detecting all repeated patterns is that all data structures used in computer science are incapable of scaling well for such purposes due to their space and time complexity. In order to analyze sequences of Megabytes the space capacity required to construct the data structure and execute the algorithm can be of Terabyte magnitude. In order to overcome such problems, my research has focused on simultaneous optimization of space and time complexity by introducing a new data structure (LERP-RSA) while the mathematical foundation that guarantees its correctness and validity has also been built and proved. A unique, innovative algorithm (ARPaD), which takes advantage of the exceptional characteristics of the introduced data structure and allows big data mining with space and time optimization, has also been created. Additionally, algorithms for single (SPaD) and multiple (MPaD) pattern detection have been created, based on the LERP-RSA, which outperform any other known algorithm for pattern detection in terms of efficiency and usage of minimal resources. The combination of the innovative data structure and algorithm permits the analysis of any sequence of enormous size, greater than a trillion characters, in realistic time using conventional hardware. Moreover, several methodologies and applications have been developed to provide solutions for many important problems in diverse scientific and commercial fields such as Finance, Event and Time Series, Bioinformatics, Marketing, Business, Clickstream Analysis, Data stream Analysis, Image Analysis, Network Security and Mathematics.Item Open Access DB-FSFO – “A Division-Based Feature Selection Flow Optimization Model for Better Summaries and Reading Recommendations(2018-11-02) Sharma, Sahil; Rokne, Jon G.; Alhajj, Reda; Kawash, JalalWith constant improvements in digital media technology, there has been a big growth in the quantity of research material available on-line for a researcher to supplement his work. An average researcher typically spends hours to study a research paper, trying to understand all its details and complexities. Sometimes this time spent is not quite justified since the paper might not be highly relevant to the reader’s research. Furthermore, this one paper might just be a small subset of the available information which a researcher would need. A researcher only has limited time and resources to deal with the challenge of accomplishing their reading goals. One approach to alleviate this is by shortening the size of a research document, thereby effectively reducing the time spent by a researcher on reading. Therefore, this thesis aims to provide a system that tackles the complex task of research text summarization. The model, DB-FSFO (Division Based – Feature Selection based Flow Optimization), makes use of Natural Language Processing tools combined with extensive Feature Extraction and Selection procedures to self-weigh the importance of various parameters of a research text document with the corpus in perspective. The final summary produced by the model is the result of a flow optimization through a Reinforcement Learning approach with an extended post-processing accuracy improvement. The model proposed in the thesis is also tested for robustness and versatility by effectively producing recommendations for the next papers to be read by the researcher. This is supplemented further by generation of a reading recommendation graph. Therefore, the DB-FSFO model makes absorbing the essentials of a research paper easier and more efficient.Item Open Access DEFINING AND COMPARING MEMORY CONSISTENCY MODELS(1997-06-01) Higham, Lisa; Kawash, Jalal; Verwaal, NathalyBecause multiprocessors implement sophisticated memory structures in order to enhance performance, processes can have inconsistent views of memory which may result in unexpected program outcomes. A memory consistency model is a set of guarantees that describes constraints on the outcome of sequences of interleaved and simultaneous operations in a multiprocessor. In this paper, we present a unifying framework to describe, understand, and compare memory consistency models. The framework is used to redefine and compare several widely used memory consistency models.Item Open Access Extracting information from Reddit for emergency management - Wildfire case(2023-12-28) Arvandi, Alireza; Alhajj, Reda; Rokne, Jon; Kawash, Jalal; Moshirpour, MohammadThe advent of social media has revolutionized the way information is disseminated and consumed during emergency situations, such as wildfires. This study provides an in-depth analysis of public sentiment and communication patterns on Reddit during wildfire events in British Columbia (BC), Canada. Utilizing a comprehensive methodological framework, the research employs data mining techniques, sentiment analysis, and comparative methods to explore the digital discourse surrounding wildfires. The methodology integrates topic mining, keyword extraction, and sentiment analysis to evaluate the nature and scope of discussions within Reddit communities. Subreddit activity is scrutinized to understand regional and national concerns, while sentiment analysis offers insights into the emotional undertones of the discussions. A comparative analysis between Reddit posts and news articles is conducted to assess the interplay between social media narratives and traditional media reporting. The findings reveal a strong regional focus in discussions, reflecting the direct impact of wildfires on local communities. National concern is also evident, with broader societal implications being discussed in both general and niche subreddits. Temporal analysis of subreddit activity indicates that engagement is predominantly event-driven, with implications for emergency services, content creators, and community managers. This research contributes to the understanding of social media’s role in crisis communication and public sentiment analysis. It highlights the potential of platforms like Reddit to serve as real-time barometers of public concern and provides actionable insights for stakeholders involved in crisis management and communication. The study’s methodologies and insights have broader applications, offering a template for analyzing online discourse in response to various emergencies.Item Open Access Flexible and Scalable Routing Approach for Mobile Ad Hoc Networks by Function Approximation of Q-Learning(2016) Elzohbi, Mohamad; Alhajj, Reda; Rokne, Jon; Kawash, Jalal; Helaoui, MohamedWireless mobile devices are rapidly spreading to the extent that it is hard to find a person not exposed to such technology. These devices could be connected directly or indirectly by wireless channels to form a mobile ad hoc network (MANET). Finding a route for flow from a source to a destination in a network is known as routing. Dynamic topology and unstable link states are the main problems facing routing in MANETs. This thesis employs reinforcement learning, namely Q-learning to develop a routing mechanism. Features inspired from the network are used in approximating the Q-function to form a new intelligent routing metric. This way, the routing process concentrates on specific routes instead of network-wide broadcasting. Accordingly, it is possible to achieve flexibility and scalability in routing. Advantages of the proposed routing technique have been highlighted by conducting experiments in two MANETs environments, namely hand-held devices based MANETs and VANETs.Item Open Access Formal Models and Implementations of Distributed Shared Memory(2009) Cheng Hum Yuen, Steven William; Higham, Lisa; Kawash, JalalItem Open Access Impact of Instruction Re-Ordering on the Correctness of Shared-Memory Programs(2005-08-26) Higham, Lisa; Kawash, JalalSequential consistency is an intuitive consistency model that simpli_es reasoning about concurrent multiprocessor programs. Most implementations of high-performance multiprocessors, however, utilize mechanisms that allow instructions to execute out of order, resulting in consistency models that are weaker than sequential consistency and further complicating the job of programmers. This paper investigates all possible combinations of re-ordering of read and write instructions and their effects on the correctness of programs that are designed for sequential consistency. It shows that with certain combinations of re-orderings, any program that accesses shared memory through only reads and writes and that is correct assuming sequential consistency, can be transformed to a new program that does not use any explicit synchronization, and that remains correct in spite of the instruction re-ordering. With other combinations of re-ordering, such transformations do not exist, and even solutions to the mutual exclusion problem are impossible without resorting to explicit synchronization.Item Open Access Implementing Sequentially Consistent Programs on Processor Consistent Platforms(2004-02-17) Higham, Lisa; Kawash, JalalDesigners of distributed algorithms typically assume strong memory consistency guarantees, but system implementations provide weaker guarantees for better performance and scalability. This motivates the study of how to implement programs designed for sequential consistency on platforms with weaker consistency models. Typically, such implementations are impossible using only read and write operations to shared variables. For example, Sparc's Total Store Order machines (and their even weaker Partial Store Order and Relaxed Memory Order machines), the PowerPC, Alpha, Java and most variants of processor consistency all require the use of strong and expensive built in hardware synchronization primitives to implement mutual exclusion. One variant of processor consistency originally proposed by Goodman and called here PC-G is an exception. It is known that PC-G provides just enough consistency to implement mutual exclusion using only reads and writes. This paper extends the study of Goodman's version of processor consistency from specific problems (such as mutual exclusion) to arbitrary ones. That is, we investigate the existence of compilers to convert programs that use shared read/write variables with sequentially consistent memory semantics, to programs that use read/write variables with PC-G consistency semantics.
We first provide a simple program transformation, and prove that it compiles any 2-process program with only single-writer variables from sequentially consistency to PC-G consistency. We next prove that no similar simple compiler exists for even a very restricted class of 2-process programs.
Even though our program transformation is not a general compiler for 3 or more processes, it does correctly transform some specific n-process programs from sequentially consistency to PC-G consistency. In particular, for the special case of the (necessarily randomized) Test&Set algorithm of Tromp and Vitanyi, our transformation extends to any number of processes. Thus, one notable outcome is an implementation of Test&Set on PC-G that uses only reads and writes of shared variables. This is the first expected, wait-free implementation of Test&Set on any weak memory model, and illustrates the use of randomization with a weak memory model.
Item Open Access JAVA: MEMORY CONSISTENCY AND PROCESS COORDINATION(1998-04-01) Higham, Lisa; Kawash, JalalIn Java, some memory updates are necessarily visible to some threads but never to others. A definition of Java memory consistency must take this fact into consideration to capture the semantics of non-terminating systems, such as a Java operating system. This paper presents a programmer-centered formal definition of Java memory behavior that captures those semantics. Our definition is employed to prove that it is impossible to provide fundamental process coordination in Java, such as critical sections and producer/consumer coordination, without the use of the synchronized and volatile constructs. However, we show that a weaker form of synchronization suffices to solve some of these problems in Java.Item Open Access Measures to Ensure Assessment Consistency(Taylor Institute Teaching Community, 2014-05-13) Kawash, Jalal; Collier, RobertItem Embargo Optimizing Pipeline Leak Detection: Leveraging Attention-based 1DCNN-BiLSTM for Enhanced Accuracy and Minimal False Alarms(2024-09-20) Khazali, Sahar; Moshirpour, Mohammad; Far, Behrouz; Drew, Steve; Kawash, JalalPipelines are an essential infrastructure for the transportation of fluids and gases in many industries. Leaks in pipelines present significant environmental and economic concerns, making accurate and timely leak detection crucial. Recent advances in deep learning, particularly sequential models, have shown promising capabilities in anomaly detection for time series data. However, the challenge remains to detect leaks accurately while minimizing false alarms. This paper presents a novel approach combining the CB-AttentionNet model, which integrates a 1D convolutional neural network (CNN), bidirectional long short-term memory (BiLSTM), and multi-head attention mechanisms to capture local and long time series dependencies. Additionally, we introduce a probabilistic search framework using Monte Carlo methods to optimize window sizes dynamically, addressing the limitations of fixed window sizes in handling variable-length sequential data. Experimental results demonstrate that our method performs better in terms of accuracy and reducing false positives across various simulations with industrial pipeline data. Optimized window sizes, particularly between 45 and 60 seconds, offer an effective balance between reducing misclassified leaks and maintaining high training accuracy. Furthermore, our analysis of resource usage and evaluation time shows that the model’s performance is efficient and manageable within typical operational constraints.Item Open Access Programmer-Centric Conditions for Itanium Memory Consistency(2006-08-17) Higham, Lisa; Jackson, LillAnne; Kawash, JalalA programmer-centric model of memory consistency provides a sequence of instructions for each proces- sor, and requires that these sequences satisfy a collection of rules. It also requires that the notion of validity of a sequence is the natural one: the value read from a shared memory location must be one that was written by the most recent preceding instruction that stored to the same location. A programmer-centric model supports reasoning about programs at a non-operational level. It is not obscured by the implementation details of the underlying architecture. In this paper, we formulate a programmer-centric description of the memory consistency model provided by the Itanium architec- ture. However, our definition is not tight. We provide two very similar definitions, each motivated by slightly different implementations of load-acquire instructions, and prove that the specification of the Itanium memory model lies strictly between the two. We also entertain a handful of other natural notions of load-acquire rules and show that none exactly captures the Itanium specification. This leads us to question whether the specification of the Itanium memory order [5] is actually faithful to the Itanium architects' intentions.Item Open Access Puzzles: Towards a Transformation of Teaching & Learning Practices(2017-05) Kawash, Jalal; Reid, LesliePuzzles are fun and can be exploited to ignite a students’ interest in their discipline, enhance problem solving, critical reasoning and create the opportunity for thought-provoking conversations. We share examples of how puzzles can be employed in post-secondary teaching. Participants also get the chance to design a puzzle activity suitable for their classes.Item Open Access Specifying Memory Consistency of Write Buffer Multiprocessors(2004-08-17) Higham, Lisa; Jackson, LillAnne; Kawash, JalalWrite buffering is one of many successful mechanisms that improves the performance and scalability of multiprocessors. However, it leads to more complex memory system behavior, which cannot be described using intuitive consistency models, such as sequential consistency. It is crucial to provide programmers with a specification of the exact behavior of such complex memories. This paper presents a uniform framework for describing systems at different levels of abstraction and proving their equivalence. The framework is used to derive and prove correct specification in terms of program-level instruction of the SPARC total store order and partial store order memories.
The framework is also used to examine the SPARC relaxed memory order. We show that it is not a memory consistency model that corresponds to any implementation on a multiprocessor that uses write-buffers, even though we suspect that the SPARC Version 9 specification of relaxed memory order was intended to capture a general write-buffer architecture. The same techniques can be used to show that coherence does not correspond to a write-buffer architecture. A corollary is that any implementation of Alpha consistency using write-buffers cannot produce all possible Alpha computations. That is, there are some computations that satisfy the Alpha specification but cannot occur in the given write-buffer implementation.Item Open Access The Virtual Faraday Cage(2013-08-09) King, James; Barker, Ken; Kawash, JalalThis thesis' primary contribution is that of a new architecture for web application platforms and their extensions, entitled "The Virtual Faraday Cage". This new architecture addresses some of the privacy and security related problems associated with third-party extensions running within web application platforms. A proof-of-concept showing how the Virtual Faraday Cage could be implemented is described. This new architecture aims to help solve some of the key security and privacy concerns for end-users in web applications by creating a mechanism by which a third-party could create an extension that works with end-user data, but which could never leak such information back to the third-party. To facilitate this, the thesis also incorporates a basic privacy-aware access control mechanism. This architecture could be used for centralized web application platforms (such as Facebook) as well as decentralized platforms. Ideally, the Virtual Faraday Cage should be incorporated into the development of new web application platforms, but could also be implemented via wrappers around existing application platform Application Programming Interfaces with minimal changes to existing platform code or workflows.Item Open Access Traffic Characterization of Social Network Applications(2021-09) Keshvadi, Sina; Williamson, Carey; Kawash, Jalal; Henry, Ryan; Brecht, Tim; Krishnamurthy, DiwakarOnline Social Networks (OSNs) are popular tools for billions of people around the globe to communicate with each other. With the popularity of mobile devices and ubiquitous network connectivity, global Internet traffic, including OSN and video streaming traffic, has grown rapidly. Many OSNs recoup their operational costs through advertising and data analytics, which raises concerns about what user-level information is collected by these sites, and where such information is sent. Understanding the network traffic generated by OSNs provides better insight into these services, and their performance. In this dissertation, we use active and passive measurement techniques to study the network traffic generated by OSNs on a large campus edge network and use the resulting insights for analysis and characterization of these applications. We designed and implemented MoVIE (Mobile Video Information Extraction), an active measurement and video streaming measurement tool, that provides visibility into the network traffic generated from a smartphone under test. We used our tool to investigate several OSN sites (e.g., Instagram, WeChat, Snapchat), as well as free live streaming (FLS) providers that share their content through online discussion social networks such as Reddit. We conducted passive measurements on a large campus edge network to analyze the properties of OSNs and characterize the traffic of these applications at scale. We identified the key characteristics of Instagram and four popular instant messaging apps on a large campus edge network. The main observations from our study indicate a rich ecosystem of online social apps, many of which exhibit strong diurnal patterns, complex user interactions, and heavy-tailed distributions for connection durations and transfer sizes. Instagram exceeded 1 TB of daily traffic volume on our campus network and the four IM apps contributed about 650 GB per day. By analyzing and characterizing the network traffic on a campus network, this dissertation provides a better understanding of OSN applications and their possible future traffic demands.