Gaga ebresafegaga

High-Performance Matrix Multiplication

This is a short post that explains how to write a high-performance matrix multiplication program on modern processors. In this tutorial I will use a single core of the Skylake-client CPU with AVX2, but the principles in this post also apply to other processors with different instruction sets (such as AVX512).

Intro

Matrix multiplication is a mathematical operation that defines the product of

With scoped effects, handlers must be a part of the program

It is seductive to imagine that effect handlers in an algebraic effect system are not part of the program itself but metalanguage-level folds over the program tree. And in traditional free-like formulations, this is in fact the case. The Eff monad represents the program tree, which has only two cases:

data Eff effs a where
  Pure :: a -> Eff effs a
  Op :: Op effs a -> (a -> Eff effs b) -> Eff effs b

data Op effs a where

This project is a tiny compiler for a very simple language consisting of boolean expression.

The language has two constants: 1 for true and 0 for false, and 4 logic gates: ! (not), & (and), | (or), and ^ (xor).

It can also use parentheses to manage priorities.

Here is its grammar in BNF format:

expr ::= "0" | "1"

	(* GADT list that exposes the type of the head element *)
	type _ hlist =
	\| Nil: 'a hlist
	\| Cons: ('a * 'b hlist) -> 'a hlist

	(* let rec len = function *)
	(* let rec len (type a) (l: a hlist): int = match l with *)
	(* both of the above result in a "type constructor would escape its scope" error *)
	(* correct version: *)
	let rec len : type a. a hlist -> int = function

	#lang racket
	(require (for-syntax syntax/parse)
	(for-meta 2 racket syntax/parse syntax/stx racket/syntax))

	(begin-for-syntax
	(begin-for-syntax

	;; attr+arity ::= id
	;; \| [id arity]
	;;

	// Algorithm W
	// From Principal Types for functional programs
	// http://web.cs.wpi.edu/~cs4536/c12/milner-damas_principal_types.pdf
	// by bkase

	// STD library
	infix operator <>: AdditionPrecedence
	extension Dictionary {
	static func <>(lhs: Dictionary, rhs: Dictionary) -> Dictionary {
	var d: [Key: Value] = [:]

	module Syn =
	struct
	type uni_level = int
	type t =
	\| Var of int (* DeBruijn indices for variables *)
	\| Nat \| Zero \| Suc of t \| NRec of t * t * t * t
	\| Pi of t * t \| Lam of t \| Ap of t * t
	\| Uni of uni_level
	\| Subst of t * subst
	and subst =

	module Elmish.Snake

	(**
	Timer as a source of events with an SVG clock, by Zaid Ajaj.
	You can find more info about Emish architecture and samples at https://elmish.github.io/
	*)

	open System
	open Fable.Import
	open Fable.Helpers.React


	var resolution = 50;

	var printerError = 0.05;


	var xsize = 100;
	var ysize = 100;
	var height = 20;

	html,
	body {
	font-size: 16px;
	}