Huawei Hackathon 2021 - Sweden (Stockholm)

Overview

huawei-hackathon-2021

Contributors

banner

Challenge

Requirements:

  • python=3.8.10
  • Standard libraries (no importing)

Important factors:

Data dependency between tasks for a Directed Acyclic Graph (DAG).

Task waits until parent tasks finished and data generated by parent reaches current task.

Communication time: The time which takes to send the parents’ data to their children, if they are located on different processing nodes; otherwise it can be assumed negligible. As a result, we prefer to assign communicating tasks on the same processing node.

Assign tasks on the same processing node where possible; if not, make data transfers from parent -> children as fast as possible.

Affinity: It refers to the affinity of a task to its previous instances running on the same processing node that can reduce overhead to initialize the task, such as a lower Instruction Cache Miss. Ideally the task is better to run on the same processing node where its previous instance was recently run.

Reuse processing nodes where possible. I.e. run children tasks on parent node.

Load Balancing of processing nodes: The CPU utilization of processing nodes should be balanced and uniformed.

Self explanitory.

Assumptions

  1. If communicating tasks assigned to the same processing node, the communication time between them is negligible, i.e., equal to 0.

    Using same node reduces communication time to 0.

  2. If the previous instance of the same task is recently assigned to the same processing node, the estimated execution time of the current instance of the task reduces by 10%. For example, if T0 is assigned to PN1, the execution time of the second instance of T0 (denoted by T0’) on PN1 is 9µs, rather than 10µs.

    Using same node reduces processing time by 10%. PN1 = Processing Node 1. T0 = Task 0.

  3. "Recently assigned" can be translated to:
    • If the previous instance of the current task is among the last Χ tasks run on the PN.
    • For this purpose we need to keep, a history of the X recent tasks which run on each PN.

      Log the tasks tracked?

  4. A DAG’s deadline is relative to its release time which denoted by di . For example, if the deadline of a DAG is 3 and the release time of its ith instance is 12, it should be completed before 15.
  5. All time units are in microseconds.
  6. The execution of tasks are non-preemptive, in the sense that a task that starts executing on a processor will not be interrupted by other tasks until its execution is completed.

    Tasks cannot run concurrently on the same processor.

Problem Formulation

Consider a real-time app including n DAGs (DAG1, DAG2, ... DAGn) each of which are periodically released with a period Pk . Instances of each DAG is released over the course of the running application. The ith instance of the kth DAG is denoted by Dk(i). The application is run on x homogenous processing nodes (PN1, PN2, ... PNx). The algorithm should find a solution on how to assign the tasks of DAGs to the PNs so that all DAGs deadlines are respected and the makespan of the given application is minimized. Makespan: The time where all instances of DAGs are completed

Questions:

Propose an algorithm to solve the considered problem to maximize the utility function including both the total application Makespan and the standard deviation of the PN utilizations (i.e., how well-uniform is the assignment) such that both task dependency constraints and DAGs deadlines are met.

Utility Function = 1 / (10 * Normalized(Makespan) + STD(PN utilizations))
Normalized(Makespan) = Makespan / Application_worst_case_completion_time
Application_worst_case_completion_time = SUM(execution_times, DAG_communication_times)
Normalized(Makespan) and STD(PN utilizations) are both values [0..1] Algorithm should specify the assignment of tasks to PNs that maximize utility function. Algorithm should specify the order the tasks are scheduled and execution order of tasks for each PN.

I/O

Input

Scheduler input: 12 test cases consisting of a JSON file that includes:

  • A set of independent DAGs
  • The deadlines for the DAGs
  • Number of instances of each DAG
  • Period (Pk) of the DAGs
  • List of tasks for each DAG
  • Execution times for each DAG
  • Communication (inter-task) times for each DAG __ --> Number of cores mentioned in each test case <--__

Output

A CSV file including:

  • The PN_id of which each task was assigned to (0, 1, ... x)
  • Order of execution of the tasks in their assigned PN
  • Start and finish time of the task
  • Applcation markspan
  • The STD of the clusters' utilization (PN utilization?)
  • Value of the utility function
  • The execution time of the scheduler on our machine.

image

Note for Python coders: If you code in Python, you need to write your own printer function to create the csv files in the specified format.

Owner
Drake Axelrod
Student at University of Göteborg studying Software Engineering & Management.
Drake Axelrod
Progressive Coordinate Transforms for Monocular 3D Object Detection

Progressive Coordinate Transforms for Monocular 3D Object Detection This repository is the official implementation of PCT. Introduction In this paper,

58 Nov 06, 2022
Only works with the dashboard version / branch of jesse

Jesse optuna Only works with the dashboard version / branch of jesse. The config.yml should be self-explainatory. Installation # install from git pip

Markus K. 8 Dec 04, 2022
banditml is a lightweight contextual bandit & reinforcement learning library designed to be used in production Python services.

banditml is a lightweight contextual bandit & reinforcement learning library designed to be used in production Python services. This library is developed by Bandit ML and ex-authors of Facebook's app

Bandit ML 51 Dec 22, 2022
UFPR-ADMR-v2 Dataset

UFPR-ADMR-v2 Dataset The UFPR-ADMRv2 dataset contains 5,000 dial meter images obtained on-site by employees of the Energy Company of Paraná (Copel), w

Gabriel Salomon 8 Sep 29, 2022
A repository built on the Flow software package to explore cyber-security attacks on intelligent transportation systems.

A repository built on the Flow software package to explore cyber-security attacks on intelligent transportation systems.

George Gunter 4 Nov 14, 2022
A baseline code for VSPW

A baseline code for VSPW Preparation Download VSPW dataset The VSPW dataset with extracted frames and masks is available here.

28 Aug 22, 2022
Tandem Mass Spectrum Prediction with Graph Transformers

MassFormer This is the original implementation of MassFormer, a graph transformer for small molecule MS/MS prediction. Check out the preprint on arxiv

Röst Lab 13 Oct 27, 2022
Encode and decode text application

Text Encoder and Decoder Encode and decode text in many ways using this application! Encode in: ASCII85 Base85 Base64 Base32 Base16 Url MD5 Hash SHA-1

Alice 1 Feb 12, 2022
A tensorflow implementation of an HMM layer

tensorflow_hmm Tensorflow and numpy implementations of the HMM viterbi and forward/backward algorithms. See Keras example for an example of how to use

Zach Dwiel 283 Oct 19, 2022
LRBoost is a scikit-learn compatible approach to performing linear residual based stacking/boosting.

LRBoost is a sckit-learn compatible package for linear residual boosting. LRBoost combines a linear estimator and a non-linear estimator to leverage t

Andrew Patton 5 Nov 23, 2022
A curated list of awesome Machine Learning frameworks, libraries and software.

Awesome Machine Learning A curated list of awesome machine learning frameworks, libraries and software (by language). Inspired by awesome-php. If you

Joseph Misiti 57.1k Jan 03, 2023
MetaAvatar: Learning Animatable Clothed Human Models from Few Depth Images

MetaAvatar: Learning Animatable Clothed Human Models from Few Depth Images This repository contains the implementation of our paper MetaAvatar: Learni

sfwang 96 Dec 13, 2022
FaceQgen: Semi-Supervised Deep Learning for Face Image Quality Assessment

FaceQgen FaceQgen: Semi-Supervised Deep Learning for Face Image Quality Assessment This repository is based on the paper: "FaceQgen: Semi-Supervised D

Javier Hernandez-Ortega 3 Aug 04, 2022
Generative Adversarial Networks for High Energy Physics extended to a multi-layer calorimeter simulation

CaloGAN Simulating 3D High Energy Particle Showers in Multi-Layer Electromagnetic Calorimeters with Generative Adversarial Networks. This repository c

Deep Learning for HEP 101 Nov 13, 2022
HistoSeg : Quick attention with multi-loss function for multi-structure segmentation in digital histology images

HistoSeg : Quick attention with multi-loss function for multi-structure segmentation in digital histology images Histological Image Segmentation This

Saad Wazir 11 Dec 16, 2022
PyTorch implementation of paper: AdaAttN: Revisit Attention Mechanism in Arbitrary Neural Style Transfer, ICCV 2021.

AdaAttN: Revisit Attention Mechanism in Arbitrary Neural Style Transfer [Paper] [PyTorch Implementation] [Paddle Implementation] Overview This reposit

148 Dec 30, 2022
A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation

Segnet is deep fully convolutional neural network architecture for semantic pixel-wise segmentation. This is implementation of http://arxiv.org/pdf/15

Pradyumna Reddy Chinthala 190 Dec 15, 2022
Weakly Supervised Segmentation with Tensorflow. Implements instance segmentation as described in Simple Does It: Weakly Supervised Instance and Semantic Segmentation, by Khoreva et al. (CVPR 2017).

Weakly Supervised Segmentation with TensorFlow This repo contains a TensorFlow implementation of weakly supervised instance segmentation as described

Phil Ferriere 220 Dec 13, 2022
Pop-Out Motion: 3D-Aware Image Deformation via Learning the Shape Laplacian (CVPR 2022)

Pop-Out Motion Pop-Out Motion: 3D-Aware Image Deformation via Learning the Shape Laplacian (CVPR 2022) Jihyun Lee*, Minhyuk Sung*, Hyunjin Kim, Tae-Ky

Jihyun Lee 88 Nov 22, 2022
This is an official pytorch implementation of Fast Fourier Convolution.

Fast Fourier Convolution (FFC) for Image Classification This is the official code of Fast Fourier Convolution for image classification on ImageNet. Ma

pkumi 199 Jan 03, 2023