Try   HackMD

2022q1 Homework1 (lab0)

contributed by < huang-me >

注意作業書寫規範！

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

Prerequisites

$ sudo apt install build-essential git clang-format aspell colordiff valgrind

Build cppcheck

Download cppcheck source code from GitHub.

# unzip file
tar -xf <cppcheck-version.tar.gz>
cd cppcheck-<version>
# build file and install
sudo make CFGDIR=/usr/share/cppcheck/ FILESDIR=/usr/bin/ -j4
sudo make install CFGDIR=/usr/share/cppcheck/ FILESDIR=/usr/bin -j4

Environment

Your gcc was too old. Upgrade your Linux distribution as soon as possible, otherwise you will encounter some unexpected issues later.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               142
Model name:          Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
Stepping:            10
CPU MHz:             899.969
CPU max MHz:         4000.0000
CPU min MHz:         400.0000
BogoMIPS:            3999.93
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            8192K
NUMA node0 CPU(s):   0-7

Development

queue_new

  • Use malloc to acquire memory space, return NULL if no space available.
    Initialize list_head with INTI_LIST_HEAD defined in list.h
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(*head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

queue_free

  • Delete first node until list have no element, and delete list_head.
void q_free(struct list_head *l)
{
    if (!l)
        return;
    while (!list_empty(l)) {
        element_t *node = list_first_entry(l, element_t, list);
        q_remove_head(l, NULL, 0);
        free(node->value);
        free(node);
    }
    free(l);
}
  • Use list_for_each_entry_safe defined in list.h to iterate through all nodes in list, remove them from list and release the memory.

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *e, *s;
    list_for_each_entry_safe (e, s, l, list) {
        list_del(&(e->list));
        q_release_element(e);
    }
    free(l);
}

q_insert_head

  • Use malloc allocate memory, return false if no memory can be allocated.
    Use memset initialize the value of newNode and copy input to newNode->value
bool q_insert_head(struct list_head *head, char *s)
{
    element_t *newNode = malloc(sizeof(element_t));
    if (!newNode)
        return false;
    newNode->value = malloc(sizeof(char) * (strlen(s) + 1));
    if(!newNode->value) {
        q_release_element(newNode);
        return false;
    }
    memset(newNode->value, '\0', strlen(s) + 1);
    strncpy(newNode->value, s, strlen(s));
    list_add(&newNode->list, head);
    return true;
}

q_insert_tail

  • Most operations are same as q_insert_head, the only difference is replace list_add with list_add_tail.
bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *newNode = malloc(sizeof(element_t));
    if (!newNode)
        return false;
    newNode->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newNode->value) {
        q_release_element(newNode);
        return false;
    }
    memset(newNode->value, '\0', strlen(s) + 1);
    strncpy(newNode->value, s, strlen(s));
    list_add_tail(&newNode->list, head);
    return true;
}

q_remove_head

  • Use list_entry to get the address of the entry.
    Copy the entry value to sp if sp is given.
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_entry(head->next, element_t, list);
    if (sp && node->value) {
        strncpy(sp, node->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    list_del(head->next);
    return node;
}

q_remove_tail

  • Most operations are same as q_remove_head, the only difference is the node position is changed from head->next to head->prev.
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_entry(head->prev, element_t, list);
    if (sp && node->value) {
        strncpy(sp, node->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    list_del(head->prev);
    return node;
}

q_release_element

  • Release the memory of e->value and e if they were defined.
void q_release_element(element_t *e)
{
    if (!e)
        return;
    if (e->value)
        free(e->value);
    free(e);
}

q_size

  • Iterate through the queue with list_for_each and count the number of elements.
int q_size(struct list_head *head)
{
    if (!head)
        return -1;
    int cnt = 0;
    struct list_head *e;
    list_for_each (e, head)
        cnt++;
    return cnt;
}

q_delete_mid

  • Use fast/slow pointer find middle element of linked list and delete it.
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    struct list_head *fast, *slow;
    fast = slow = head->next;
    while (slow->next != head && slow->next->next != head) {
        slow = slow->next->next;
        fast = fast->next;
    }
    element_t *e = list_entry(fast, element_t, list);
    list_del(fast);
    q_release_element(e);
    return true;
}

q_delete_dup

  • Iterate through all list nodes, delete the node if value is same as last node.
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    element_t *e, *s;
    char *last = NULL;
    list_for_each_entry_safe (e, s, head, list) {
        if (last && strcmp(last, e->value) == 0) {
            list_del(&e->list);
            q_release_element(e);
        } else {
            last = strdup(e->value);
        }
    }
    return true;
}

strdup may lead to memory leak since the space is never released.
Rewrite q_delete_dup as following code to prevent copying data.

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    element_t *e, *s;
    char *last = NULL;
    list_for_each_entry_safe (e, s, head, list) {
        if (last && strcmp(last, e->value) == 0) {
            list_del(&e->list);
            q_release_element(e);
        } else {
            last = e->value;
        }
    }
    return true;
}

q_swap

  • Reassign all pointers between list nodes.
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;
    struct list_head *e = head->next;
    while (e != head && e->next != head) {
        struct list_head *n;
        n = e->next;
        n->next->prev = e;
        e->next = n->next;
        n->next = e;
        n->prev = e->prev;
        e->prev->next = n;
        e->prev = n;
        e = e->next;
    }
}

Shorten code with use of list.h functions.

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;
    struct list_head *e = head->next;
    while (e != head && e->next != head) {
        struct list_head *n = e->next;
        list_del(n);
        list_add(n, e->prev);
        e = e->next;
    }
}

q_reverse

  • Exchange all node's next and prev pointer to achieve reverse.
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *e, *s;
    list_for_each_safe (e, s, head) {
        e->next = e->prev;
        e->prev = s;
    }
    struct list_head *tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

q_sort

  • Split list into two subqueues, sort them separately and Merge into one queue.
    Time complexity: O(nlogn)
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *fast, *slow;
    fast = slow = head->next;
    while (fast != head && fast->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }
    if (fast == head)
        fast = fast->prev;

    struct list_head *mid;
    mid = slow->prev;
    head->prev = mid;
    mid->next = head;
    q_sort(head);
    struct list_head *front, *last;  // ptr for 1st subqueue
    front = head->next;
    last = head->prev;
    head->next = slow;
    slow->prev = head;
    head->prev = fast;
    q_sort(head);
    struct list_head *fr;  // ptr for 2nd subqueue
    fr = head->next;
    last->next = fr;
    fr->prev = last;
    head->next = front;
    front->prev = head;

    // merge two subqueue
    struct list_head *p1 = front, *p2 = last->next;
    while (p1 != last->next && p2 != head) {
        char *v1 = list_entry(p1, element_t, list)->value,
             *v2 = list_entry(p2, element_t, list)->value;
        if (strcmp(v1, v2) <= 0) {
            p1 = p1->next;
        } else {
            struct list_head *tmp = p2->next;
            list_del(p2);
            p2->next = p1;
            p2->prev = p1->prev;
            p1->prev = p2;
            p2->prev->next = p2;
            p2 = tmp;
        }
    }
}

Shorten merge code with use of list.h function.

    struct list_head *p1 = front, *p2 = last->next;
    while (p1 != last->next && p2 != head) {
        char *v1 = list_entry(p1, element_t, list)->value,
             *v2 = list_entry(p2, element_t, list)->value;
        if (strcmp(v1, v2) <= 0) {
            p1 = p1->next;
        } else {
            struct list_head *tmp = p2->next;
            list_del(p2);
            list_add(p2, p1->prev);
            p2 = tmp;
        }
    }

Result

make test
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---	trace-05-ops	6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, and sort
---	trace-06-ops	6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---	trace-07-string	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

Insert/Remove time complexity test doesn't always pass in GitHub CI.

You should read the paper and recognize the root cause.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

Fisher-Yates shuffle

  • Add q_shuffle into queue.c
  • Fisher-Yates shuffle steps
    1. Randomly choose a node and move it to tail of the queue.
    2. Repeat step 1 for q_size times
void q_shuffle(struct list_head *head) {
    if(!head || list_empty(head))
        return;
    struct list_head *node;
    for(int cnt=q_size(head); cnt>0; cnt--) {
        int x = rand() % cnt;
        node = head->next;
        for(int i=0; i<x; i++)
            node = node->next;
        list_del(node);
        list_add_tail(node, head);
    }
    return;
}
  • Add q_shuffle definition into queue.h header file.
void q_shuffle(struct list_head *head);
  • Add do_shuffle in qtest.c.
static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    q_shuffle(l_meta.l);
    show_queue(3);
    return !error_check();
}
  • Add command shuffle to console
ADD_COMMAND(shuffle, "                | Shuffle the queue");
Last changed by 
 
huang-me
0
330

Read more

Parallel programming HW5

&#x5B78;&#x865F;&#xFF1A;311551173 &#x59D3;&#x540D;&#xFF1A;&#x9EC3;&#x7267;&#x6069; Q1 What are the pros and cons of the three methods? Give an assumption about their performances. Method 1 Pros: &#x6BCF;&#x4E00;&#x500B;thread&#x53EA;&#x9700;&#x8981;&#x8655;&#x7406;&#x4E00;&#x500B;pixel Cons: &#x6709;&#x4E9B;&#x8A08;&#x7B97;&#x91CF;&#x5C0F;&#x7684;thread&#x53EA;&#x88AB;&#x4F7F;&#x7528;&#x4E00;&#x4E0B;&#xFF0C;&#x53EA;&#x6709;&#x90E8;&#x5206;&#x7684;thread&#x6703;&#x56E0;&#x70BA;&#x8A08;&#x7B97;&#x91CF;&#x8F03;&#x5927;&#x800C;&#x88AB;&#x4F7F;&#x7528;&#x8F03;&#x4E45;&#xFF0C;&#x5C0E;&#x81F4;&#x6574;&#x9AD4;thread utilization&#x8F03;&#x4F4E;

Dec 13, 2022
Parallel programming HW4

Q1.1: How do you control the number of MPI processes on each node? MPI run programs according to hostfile, it assign programs to machine in hostfile one-by-one. machine_1 machine_1 machine_2 If we&apos;re going to run 8 copies of the program and hostfile is defined as above, program_1 &amp; program 2 will be assigned to machine_1, program_3 will be assigned to machine_2, program_4 will be assigned to machine_1, ...etc.

Nov 27, 2022
Parallel programming HW2

Q1: Is speedup linear in the number of threads used? In your writeup hypothesize why this is (or is not) the case? Refer to the graph above, the speedup is almost linear. Since all threads doing same thing, using more thread will reduce the loading of threads, which decrease the execution time linearly. Speedup is also almost linear too. Q2: How do your measurements explain the speedup graph you previously created?

Oct 21, 2022
〈Concurrency Primer〉校訂和範例撰寫

Contributed by &lt; huang-me &gt; &#x4F7F;&#x7528; atomic &#x8207;&#x5426;&#x5DEE;&#x7570; #include &lt;stdatomic.h&gt; int v = 0; atomic_bool v_ready = false; int bv; void *threadA() {

Jun 1, 2022
Read more from huang-me
Published on HackMD