Matt Chung's Site

Author: mattchung

  • Distributed Systems Introduction notes

    Distributed Systems Introduction notes

    The main take away with the introduction to distributed systems lectures is that as system designers, we need to carefully inspect our program and identify what events in our system can run concurrently (as well as what cannot run concurrency or must be serialized). To this end, we need to identify what events must happen before other events. And most importantly, we should only consider running distributed systems to increase performance when the time it takes to process an event exceeds the time it takes to send a message between nodes. Otherwise, just stick to local computation.

    Key Words: happened before, concurrent events, transitive

    Introduction

    Summary

    Lots of similarity between parallel systems and distributed systems. Symbiotic relationship between hardware and software (protocol stack)

    Quiz: What is a distributed system?

    Summary

    Distributed systems are connected via a LAN/WAN, communicate only via messages, and message time is greater than the event time (not sure what this means really)

    Distributed Systems Definition

    Summary

    Key Words: event computation time, message transmission time; Third property is that message communication time is significantly larger than the event computation time (on a single node). Leslie’s definition is: A system is distributed if the message transmission time (TM) is not negligible to the time between events in a single process. The main take away is that the algorithms or applications run on distributed noes must take longer (in computation time) than the communication otherwise no benefit of parallelism.

    A fun example

    Summary

    Key Words: happened before relationship; Set of beliefs ingrained in a distributed system example. Within a single process, events are totally ordered. Second belief is that you cannot receive the receipt of a message until after the initial message is sent.

    Happened Before Relationship

    Happened Before Event description

    Summary

    The happened before relationship means one of two things. For events A and B, it means that 1) A and B are in the same process or 2) A is the sender of the message and B is the receiver of the message

    Quiz Relation

    Summary

    You cannot assume or say anything about the order of A and B

    Happy before relationship (continued)

    Summary

    When you cannot assume the ordering of events, they might be concurrent. One event might run before the other during one invocation. Then perhaps the order gets flipped. So, these types of events are not happened before, no apparent relationship between the two events. But my question is: what are some of the synchronization and communication and timing issues that he had mentioned?

    Identifying Events

    Identifying concurrent and dependent and transitive events

    Summary

    Remember the events that “happened before” are not only between processes but within processes themselves. Also, two concurrent events are basically when we cannot guarantee whether or not an event in process A will run before an event in process B, again between processes

    Example of Event Ordering

    Summary

    Basically the events between processes can be concurrent since there’s no guarantee in terms of wall clock time when they will execute, no ordering

  • What’s the point of the parity flag in the dissemination barrier?

    What’s the point of the parity flag in the dissemination barrier?

    I’m implementating the dissemination barrier (above) in C for my advanced OS course and I’m not quite sure I understand the pseudo code itself. In particular, I don’t get the point of the parity flag …. what’s the point of it? What problem does it solve? Isn’t the localsense variable sufficient to detect whether or not the threads (or processes) synchronized? I’m guessing that the parity flag helps with multiple invocations of the barrier but that’s just a hunch.

  • First day of moving to Renton & Daily Review – Day ending in 2020/10/01

    First day of moving to Renton & Daily Review – Day ending in 2020/10/01

    My body aches from the first day of moving houses, my body sore from all the loading and unloading of tightly packed boxes from the house and into the back of the 15″ foot U-Haul truck.

    Rant

    • U-Haul at Burien employes some of the most unprofessional staff with the worst customer service. The staff were not only rude to customers but extremely denigrating to one another, the manager even shaming her employee in front of customers, the manager saying (and I quote): “You are just not doing a very good job today are you?”

    No electricity

    • Stepped into our new home and I immediately noticed that the lights didn’t flicker on when I hit the switch.  I had also noticed that the digital clock on the stove was not displaying the time. No electricity.
    • Called Puget sound energy (PSE) over the phone and within 5 minutes of talking to the representative, had them activate the electricity. They mentioned it would take up to 24 hours maximum

     

  • Learning how to build a personal brand (two books I picked up)

    Learning how to build a personal brand (two books I picked up)

    I want to learn how to better market myself and what it means to create my own personal brand and how I might be able to apply these marketing skills in my career (as a software developer and computer scientist) and as a writer. Because I do wonder what sort of impact and influence I would have if I applied even an ounce of marketing or branding.

    I’m planning on sinking my teeth into two different marketing books. My guitar instructor had recommended Seth Godin’s This is Marketing and a hacker news user recommended an e-book titled Authority by (someone I’ve never heard of) named Nathan Barry. I’ll take a crack at these two books and report back on the main takeaways and whether or not I recommend you reading them.

    At this moment in time, I have no clue what it means to build a personal brand (in all honestly I don’t even know what a personal brand means). Nonetheless, I do think learning about a little marketing and branding (really what’s the difference between the two) will be a worthwhile, non-technical skill to develop since I’d like down the line to become a full time writer and teacher and think marketing and branding will play a key role in making that happen.

  • Daily Review – Day ending in 2020/09/29

    Daily Review – Day ending in 2020/09/29

    Yesterday … was exhausting. A few times throughout the day I actually felt my body shut down and I nearly fell asleep while working. Although I cumulatively got like 7.5 hours of sleep, my sleep was constantly interrupted since Elliott has been (presumably) teething and letting out these screams at 1:00 AM and 3:00AM and 04:00 AM, the screams piercing through out thin walls and echoing throughout the rest of the house.

    On top of all this, I felt so overwhelmed with the house move, knowing that we only have just a few days left and there’s so much left to do still. But fortunately Jess and I partnered up and split some tasks up between the two of us. That really helped.

    What did I learn

    • The last true symmetric multiprocessor machine was around the late 1980s. I thought that they were much more prevalent but it appears that most of the hardware today run on non uniformed memory access (NUMA) machines
    • How to identify and trace concurrent events between processes (a little more difficult than I had originally anticipated) using a good old pen and paper

    Politics

    • Watched about 30 minutes of the first debate between Joe Biden and Donald Trump. Honestly, it’s like watching a circus. Trump constantly interrupts Joe Biden and Joe Biden often goes completely off topic. For example, while talking about his position on supporting the military, he brings up the fact that his son served in the military and currently recovering from drug addiction. While nice to know …. I wonder, it’s totally irrelevant to the conversation.

    Family and Friends

    • Jess and I operated as a team yesterday. Together in the morning, we signed an hours worth of paperwork with a notary sent by the escrow company. After, we divided and conquered. She and Elliott performed the final walk through in Renton while I sorted out how to get us internet (so painful dealing with internet sales representatives) and then I drove to Wells Fargo for my scheduled appointment to transfer the big amount for the down payment of the house.

    Interesting Quotes or Idioms

    • Prime the pump (from video lecture series in Distributed System, Quiz on “relation”)

     

  • OpenMP tutorial notes (Part 1)

    OpenMP tutorial notes (Part 1)

    I’m watching the YouTube learning series called “Introduction to OpenMP” in order to get a better understanding of how I can use the framework for my second project in advanced operating systems. You might find the below notes useful if you don’t want to sit through the entire video series.

    Introduction to OpenMP: 02 part 1 Module 1

    Moore’s Law

    Summary

    Neat that he’s going over the history, talking about Moore’s Law. The key take away now is that hardware designers are now going to optimize for power and software developers have to write parallel programs: there’s no free lunch. No magic compiler that will take sequential code and turn it into parallel code. Performance now c

    Introduction to OpenMP – 02 Part 2 Module 1

    Concurrency vs Parallelism

    Summary

    The last step should be picking up the OpenMP Library (or any other parallel programming library). What should be done firs and foremost is breaking down your problem (the act of this has not been able to automated) into concurrent parts (this requires understanding of the problem space) and then figure out which can run in parallel. Once you figure that out, then you can use compiler syntactical magic (i.e. pragmas) to direct your compiler and then sprinkle some additional pragmas that will help the compiler tell where the code should enter and where it should exit.

    Introduction to OpenMP – 03 Module 02

    OpenMP Solution Stack

    Summary

    It’s highly likely that the compiler that you are using already supports OpenMP. For gcc, pass in -fopenmp. And then include the prototype, and add some syntactic sugar (i.e. #pragma amp parallel) which basically gives the program a bunch of threads.

    Introduction to OpenMP: 04 Discussion 1

    Shared address space

    Summary

    OpenMP assumes a shared memory address space architecture. The last true SMP (symmetric multi-processor) machine was in the late 1980s so most machines now run on NUMA (non uniformed multiple access) architectures. To exploit this architecture, we need to schedule our threads intelligently (which map to the same heap but contain different stacks) and place data in our cache’s as close as possible to their private caches. And, just like the professor said in advanced OS, we need to limit global data sharing and limit (as much as possible) the use of synchronization variables since they both slow down performance

    Programming Shared Memory
  • Daily Review – Day ending in 2020/09/28

    Daily Review – Day ending in 2020/09/28

    Questions I thought about during the day

    • How did society overcome the Spanish Flu and how did the people during that time return back to normal? I doubt some vaccination ended the pandemic… so how did we all get over it? And how will it be the same (or different) this time around with COVID-19 ?

    Feelings

    • Excited to watch lectures on Distributed Systems a topic I’ve been interesting in for a very long time. Funny how I actually build distributed systems at work but don’t have my computer science foundation on the topic except I’ve done one off research on CAP theorem etc
    • Throughout the entire day I was just extremely fatigued from waking up due to screams that little Elliott let out throughout the night. I’m guessing she’s teething?

    What did I learn

    • How to use pragma C preprocessor with OpenMP. Although at work we have some pragma definitions, I haven’t myself dove into why and how. I’m still confused as to the exact details of the pragma definitions but seems like (in this particular case) that by putting in pragma omp parallel, we are signaling the compiler to inject some code that will run once on each processor

    Family and Friends Matter

    • Walked the dogs at Northacres park with little Elliott and Jess. Elliott looked super cute with the neon orange beanie that her mom bought her on Amazon

    Graduate School

    • Glad I took the exam the day before yesterday (instead of yesterday, when the window to take the exam closes) since I was completely drained of energy yesterday. Honestly, if I had taken the exam last night, I’m pretty confident I would’ve bombed it
    • Watched a couple lecture videos on Distributed Systems and learned a couple new terms like event computation time and message computation time
    • Watched the first couple video tutorials on OpenMP, the YouTube learning series taught by Tim Mattson, one of the original and core developers of the library.

    Administrative

    • Disassembled our wooden kitchen table using my Makita drill and the allen wrench adapter. I broke down the table so that it would fit inside the 3 yard waste bin that I rented from Seattle Public Utilities for the week. My hope is that we dump our unnecessary junk instead of packing them into boxes and hauling it to the new house
    • Scheduled a 20 ft. U-Haul truck for the move. I had to call into the help line because I want a one way drop-off (i.e. from Seattle to Renton) but their website doesn’t currently allow you to extend the number of days you are renting a truck. I also learned that U-Haul has very low inventory and they currently forbid renting trucks for more than one day (unless it’s a one way drop off)
    • Confirmed two appointments for the day: in person notary (due to COVID-19) for signing paperwork for the house and Wells Fargo appointment to transfer escrow money.

    Work

    • Lots of back to back meetings yesterday and some unexpected ones (e.g. a 05:30 pm invite for a project that I’m leading)
    • Added some counters to my code to verify the behavior of my new feature that I’m developing
  • Project 2 (barrier synchronization) – Snapshot of my knowledge

    Project 2 (barrier synchronization) – Snapshot of my knowledge

    The purpose of this post is to take a snapshot of my understanding before I begin working on project 2: implementing (two) synchronization barriers. Although I picked up some theoretical knowledge from both this course (i.e. advanced operating systems) and GIOS (i.e. graduate introduction to operating systems) on barrier synchronization, I actually never implemented barriers so I’m very much looking forward to working on this project and bridging the gap between theory and practice.

    What I do know

    • Conceptual understanding of the various types of barriers (e.g. centralized, tree based, MCS, tournament, dissemination)
    • Purpose of sense reversal (i.e. determine which barrier one is in)
    • Advantages of using an MCS barrier over a dissemination barrier when using a shared memory bus due to serialization and lack of parallel messages

    What I don’t know

    • What OpenMP is and how it is different than MPI. Are the two the same or related somehow?
    • How the various barriers will perform based on the architecture (i.e. 8 way shared multi-processor system)
    • How to hook the barriers into some higher level user application? Will I be using the barriers for a producer/consumer type of application? Will I need to write that application or just the barrier itself?
    • What primitives will be available? Will I need to leverage some hardware atomic operations (my guess is yes)
  • Daily Review – Day ending in 2020/09/27

    Daily Review – Day ending in 2020/09/27

     

    Writing

    Family and Friends

    • Walked the dogs at Magnuson Park. Elliott and Jess joined too since Elliott has been waking up so early these days (around 05:45 AM). Trying to get the dogs to capitalize on these amazing off leash parks in North Seattle, before we move to Renton (in just a few days)
    • Cancelled war room meeting so that I could instead so I could have a pizza party with my next door neighbors and their two children. My neighbor’s daughter in particular was really looking forward to having a picnic party since there’s only a few days left until my wife and I and the rest of our entire pack move to Renton. Upon reflection, cancelling the war room was the right decision since I’ll remember this pizza party for years to come.
    • Took Elliott to Maple Leaf Park for about 20 minutes. She loves loves loves sitting on the kitty bridge and watching other kids play. Seriously. She’ll sit there and just smile at them, completely happy to just be outside. I never thought I would enjoy being a father so much. Honestly, I would’ve thought that taking my kids to the park would be boring and feel like an obligation but it’s just the opposite.
    • During dinner Elliott sat in her own little chair like a little adult for the first time, following Avery’s lead
    • Took Elliott with me to The Grateful Bread to pick up challah for Jess while she received in home physical therapy. After buying a couple loafs, Elliott and I sat outside of the cafe, her on my lap while I was wearing a mask (again, still in the midst of the COVID-19 pandemic). Felt nice just to sit outside and tear up little pieces of Challah for her to eat

    Graduate School

    • Crammed heavily for the mid term exam (below). Took the exam last night instead of today (which is a good call since I’m absolutely shattered today, my sleep interrupted several times because I was still able to hear Elliott let out war like screams throughout the night … I think she’s teething)
    • Took the remotely proctored exam for advanced operating systems (AOS). I really think that studying with the Anki software for about an hour paid off. Otherwise, I don’t think I would’ve been able to answer questions around Exokernel and questions around the hypercalls.

    Music

    • Had another wonderful guitar lesson yesterday with Jared. We focused on going over new inversions that should spice up some of my song writing since I feel like I’m in a rut these days, all my songs sorted of sounding the same since I’m playing them in the same voicings. But I should take a moment and step back and appreciate that I can even write songs and can even apply music theory that I picked up over the last couple years
    • Jared and I got to talking about marketing and he mentioned an author called Seth Godin and how (without realizing it) I’m sort of applying the techniques from his book. In any case, I should check out that author’s book (just no time right now).

    Miscellaneous

    • Packed up my wide monitors and mechanical keyboard that were previously laid out desk office. Just a couple more days until we are out of this house in Seattle and moving to Renton

     

  • Weekly Review: week ending in 2020/09/27

    Weekly Review: week ending in 2020/09/27

    This past week, I skipped writing my daily reviews for two days in a row because I was really pressed for time. On the days that I skipped, I immediately started studying for the midterm exam as soon as I woke up. Looking back, I regret not writing anything down. Because I’ve already forgotten the events from those days, the memories lost.

    In the future, when I’m under the gun I think I should still do my daily reviews going even if that means typing out only 5 bullet points. To that end, I’m going to limit the time for my daily reviews and return to time bounding the activity to 15 minutes. I’m hoping that setting an upper bound on those reviews will encourage me to rapidly write something (or anything) down, which is much better than writing nothing down.

    Looking back at last week

    Writing

    • Published 4 daily reviews (missing Friday and Saturday reflections)
    • Introduced a “what did I learn” section in my reviews (super helpful to capture the knowledge I acquired, even if they are in small doses)

    Graduate School

    • Launched an online study group (i.e. war room) so us students could collaborate over video in preparation for the upcoming midterm. Overall, the war rooms were super beneficial (and fun as well), not only for me but for others. Lots of discussions happened. Made me re-realize that although writing does help solidify my understanding of a subject so does speaking about the topic. Also, hearing people’s others questions and answers help me understand the material more deeply.

    Things I learned

    • To build high performance parallel systems we want to limit sharing global data structures. By reducing sharing, we limit locking, an expensive operation.
    • Heavy use of typedef keyword with enums creates cleaner C code
    • Learned that hierarchical locking (or locking in general) hinders system performance, preventing concurrency. What should we do instead? Reference counting for existence guarantee.
    • Writing a simple line parser in C one has to protect against so many edge cases
    • Most of the C string functions return pointers (e.g. strnstr for locating substring)
    • Learned how you can ensure that you are not statically creating a large data structure by using the -w-larger-than=byte_size compiler option
    • Able to visualize what an IPv6 data structure looks like underneath the hood: 16 char bytes. Also these are big endian, the least significant bit starting first.
    • Writing a simple line parser in C one has to protect against so many edge cases
    • Most of the C string functions return pointers (e.g. strnstr for locating substring)
    • Learned how you can ensure that you are not statically creating a large data structure by using the -w-larger-than=byte_size compiler option
    • Able to visualize what an IPv6 data structure looks like underneath the hood: 16 char bytes. Also these are big endian, the least significant bit starting first.