Published June 25, 2020 © CC BY

Have an unused Raspberry Pi or other SBC?

If you have some unused Raspberry Pi or other single board computer waiting in the shelf, use it to build a computing grid.

IntermediateProtip4 hours1,289

Have an unused Raspberry Pi or other SBC?

Things used in this project

Hardware components

Hardkernel XU4Q

Raspberry Pi 2 Model B

Story

That nice XU4Q on the picture above was not waiting in a shelf. I bought it when I saw that it had a special price in Hardkernels shop. But an old Windows tablet and a Raspberry Pi 2 were laying unused in my shelf. What to do with 16 CPU cores? Use them for experiments with grid computing!

Is it a Cluster or is it a Grid?

It will use my (W)LAN and not the internet - that's an argument for a cluster. But it uses heterogenous hardware, isn't centrally managed, every node can operate independently, and I will write the software so that it doesn't trust the nodes - let's call it a grid.

Preparing the Grid Nodes

I need at least Java 11 on the nodes. For the Windows tablet and the Raspberry Pi 2 I downloaded it from Azul. For older Raspberry Pis on their Zulu Community Downloads page choose "Java 11 (LTS)", "Linux", "ARM 32-bit HF" and "JDK" as filters. On the XU4Q a sudo apt install openjdk-11-jre-headless does the job.

I want that the nodes run and run and run with high CPU load. For the Windows tablet there is not much what I can do. But on the Raspberry Pi and on the XU4Q I installed log2ram to reduce the wear of the SD card. With cd /var/log and sudo du -sh . I first checked the size of the logs. On the XU4Q they were quite big, so I cleaned them with sudo journalctl --rotate and sudo journalctl --vacuum-time=1s.

Then I installed log2ram:

cd git clonehttps://github.com/azlux/log2ram.gitcd log2ram/ chmod +x install.sh sudo ./install.sh sudo reboot

The XU4Q has 8 cores and a passive heatsink. To reduce the thermal stress on the CPU I activated the Ondemand governor (a service that chooses the CPU frequency depending on the load) with sudo systemctl enable ondemand and sudo systemctl start ondemand.

And I reduced the maximum CPU frequency. I created a file with the following contents:

#! /bin/bash cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_max_freq for file in /sys/devices/system/cpu/cpu*/cpufreq/scaling_max_freq; do echo "1300000" > $file; done cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_max_freq

and executed it with sudo. Be careful: Setting unsupported CPU frequencies can damage your hardware. The XU4Q has four A15 cores and four A7 ones. The value 1300000 (corresponding to 1.3 GHz) is ok for all eight cores.

Next, I downloaded tiles-11.0-jar-with-dependencies.jar from https://bitbucket.org/amotzek/tiles-11/downloads/ on all the nodes. On Linux I started the JAR with nohup java -server -jar tiles-11.0-jar-with-dependencies.jar -headless &. After verifying the output with tail -f nohup.out, I deleted nohup.out and logged out.

Using the Grid

The grid can be used with Calc, the Lisp spreadsheet. I published it here on Hackster.io for the "Pi Day" contest in 2017. Besides calculating Pi it also has some features for distributed computing, especially for remote evaluation. You can download it as calc-11.0-jar-with-dependencies.jar from https://bitbucket.org/amotzek/calc-11/downloads/.

On a computer in the same LAN as your grid nodes you start Calc with either a double-click on the JAR file or with java -jar calc-11.0-jar-with-dependencies.jar in a console.

Select cell A1 and type (get-places) into the textarea at the bottom of the window. The first call to get-places starts the subsystem for recognizing grid nodes. It also waits half a minute. That's because the grid nodes announce themselves every 30 seconds.

If your grid contains some more nodes the result from (get-places) is too long to be displayed in the cell - indicated by the little rhombus. Then you can double-click the cell or use the menu Cell > Magnify to see the value in a separate window. Above you can see the list of my four grid nodes.

Now let's give the grid nodes some work to do. Select cell A2 and enter (at (first @a1) (+ 2 3)). The result should be 5.

What happened here? at is a special form that takes two arguments. The first one is a place - one of your grid nodes. And the second argument is a piece of code that should be evaluated at that place. (first @a1) is the first element of the list of your grid nodes in cell A1. And (+ 2 3) is the sum of 2 and 3.

Maybe you think "Hey, that's lame. I don't need a grid for computing the sum of 2 and 3.". Yes, that's right. So, let's find the prime factors of 1361129477984805314731035883700620113667. If you can do that by mental calculation too, you can stop reading here :-)

Factoring Numbers

In the attachments section of this project you find the file distributed-factorization.sheet.xml. Download it and open it in Calc via the menu File > Open. Finding the prime factors will take some seconds. The result is in cell B1: (7 181 313 1171 2341 31357 565111 1046371 67525252471).

The program uses the elliptic-curve factorization method and is fast if the prime factors are small. The size of the input number doesn't affect the needed time so much.

You can inspect the factorization program and its modules via the menu Sheet > Show Program and Sheet > Show Modules and use it as inspiration for your own distributed programs running on a grid.

The documentation of the Lisp dialect can be found here (sorry, German language only). Happy hacking!

distributed-factorization.sheet.xml

<sheet><cell><column>A</column><row>1</row><formula>(+ (expt 3 65) (expt 4 65))</formula></cell><cell><column>B</column><row>1</row><formula>(sort (factorize @a1) less?)</formula></cell><cell><column>C</column><row>1</row><formula>(length (write-to-string @a1))</formula></cell><cell><column>D</column><row>1</row><formula>(apply * @b1)</formula></cell><cell><column>E</column><row>1</row><formula>(equal? @a1 @d1)</formula></cell><program>(defproc remote-search-factor (place product)
  (catch-and-apply
    (quote io-error)
    (lambda (name value)
      (if
        (member? place (get-places))
        (sleep 30000)
        (throw name value)))
    (at place (elliptic-curve-search-factor product))))

(defproc remote-thread-count (place)
   (catch-and-apply
     (quote io-error)
     (lambda (name value) 0)
     (max 1 (- (at place *thread-count*) 1)))
)

(defproc non-trivial-divisor? (factor product)
  (and
    (integer? factor)
    (greater? factor 1)
    (less? factor product)
    (integer? (/ product factor))))

(defproc remote-find-factor (place product channel)
  (dotimes (index (remote-thread-count place))
    (go
      (loop
        (when (closed-channel? channel)
          (return nil))
        (awhen
          (remote-search-factor place product)
          (when
            (non-trivial-divisor? it product)
            (send-on-channel channel it nil))
          (return nil))))))

(defproc distributed-find-factor (product)
  (let
    ((channel (make-channel 1))) 
    (ensure
      (dolist (place (cons nil (get-places)) (receive-from-channels (list channel) nil))
        (remote-find-factor place product channel))
      (close-channel channel))))

(defproc factorize (number)
  (if
    (less? number 2)
    nil
    (if
      (prime? number)
      (list number)
      (aif
        (trial-division-search-factors number)
        (append it (factorize (/ number (apply * it))))
        (let
          ((factor (distributed-find-factor number)))
          (append
            (factorize factor)
            (factorize (/ number factor))))))))</program><module><name>expt</name><version>1</version><uri>local:expt</uri><comment-de>Die Funktion expt erwartet zwei Argumente. Sie berechnet die Potenz erstes Argument hoch zweites Argument.</comment-de><comment-en></comment-en><export>expt</export><body>(defproc expt (x e)
  (cond
    ((not (integer? e))
      (throw (quote error) &quot;exponent must be an integer&quot;))
    ((= e 0) 
      1)
    ((= e 1) 
      x)
    ((&lt; e 0) 
      (/ 1 (expt x (- e))))
    (t
      (let
        ((half-e (/ e 2)))
        (if
          (integer? half-e)
          (let
            ((half-expt (expt x half-e)))
            (* half-expt half-expt))
          (* x (expt x (- e 1))))))))

(assert &quot;raised by zero&quot;
  (equal? (expt 0 0) 1))

(assert &quot;raised by one&quot;
  (equal? (expt 3 1) 3))

(assert &quot;two raised by five&quot;
  (equal? (expt 2 5) 32))

(assert &quot;two raised by minus 2&quot;
  (equal? (expt 2 -2) 1/4))</body></module><module><name>residue-class</name><version>4</version><uri>local:residue-class</uri><comment-de>Klassen und Methoden fr Restklassenringe</comment-de><comment-en></comment-en><export>residue-class-ring</export><export>residue-class</export><export>initialize</export><export>get-modulus</export><export>get-ring</export><export>same-ring?</export><export>get-value</export><export>zero?</export><export>add</export><export>sub</export><export>times</export><export>quotient</export><body>(defstruct residue-class-ring (modulus)
  (and
    (integer? modulus)
    (greater? modulus 1)))

(defmethod get-modulus ((this residue-class-ring))
  t
  (. this modulus))

#| residue class |#

(defclass residue-class ())

(defmethod initialize ((this residue-class) (ring residue-class-ring) value)
  (integer? value)
  (progn
    (.= this ring ring)
    (.= this value
      (with-slots-read-only (modulus) ring
        (if
          (&lt; value 0)
          (let
            ((pos-value (+ modulus (rem value modulus))))
              (if
                (= pos-value modulus)
                0
                pos-value))
            (rem value modulus))))
    (freeze this)))

(defmethod get-ring ((this residue-class))
  t
  (. this ring))

(defmethod get-value ((this residue-class))
  t
  (. this value))

(defmethod same-ring? ((this residue-class) (that residue-class))
  t
  (= (get-ring this) (get-ring that)))

(defmethod add ((this residue-class) (that residue-class))
  (same-ring? this that)
  (new residue-class
    (get-ring this)
    (+ (get-value this) (get-value that))))

(defmethod sub ((this residue-class) (that residue-class))
  (same-ring? this that)
  (new residue-class
    (get-ring this)
    (- (get-value this) (get-value that))))
  
(defmethod times ((this residue-class) (that residue-class))
  (same-ring? this that)
  (new residue-class
    (get-ring this)
    (* (get-value this) (get-value that))))

(defmethod quotient ((this residue-class) (that residue-class))
  (same-ring? this that)
  (new residue-class
    (get-ring this)
    (* (get-value this) 
       (catch-and-apply
         nil
         (lambda (name value)
           (throw 
             (quote no-multiplicative-inverse)
             (get-value that)))
         (modinv 
           (get-value that)
           (get-modulus (get-ring this)))))))

(defmethod zero? ((this residue-class))
  t
  (zero? (get-value this)))

#| unit test |#

(assert &quot;4 + 6 = 3 modulo 7&quot;
  (let
    ((ring (new residue-class-ring 7)))
    (= 
      (get-value 
        (+ (new residue-class ring 4) 
           (new residue-class ring 6)))
      3)))

(assert &quot;1 - 5 = 3 modulo 7&quot;
  (let
    ((ring (new residue-class-ring 7)))
    (= 
      (get-value 
        (- (new residue-class ring 1) 
           (new residue-class ring 5)))
      3)))

(assert &quot;2 * 4 = 1 modulo 7&quot;
  (let
    ((ring (new residue-class-ring 7)))
    (= 
      (get-value 
        (* (new residue-class ring 2) 
           (new residue-class ring 4)))
      1)))

(assert &quot;1 / 4 = 2 modulo 7&quot;
  (let
    ((ring (new residue-class-ring 7)))
    (= 
      (get-value 
        (/ (new residue-class ring 1) 
           (new residue-class ring 4)))
      2)))</body></module><module><name>elliptic-curve</name><version>0</version><uri>local:elliptic-curve</uri><comment-de>Eine elliptische Kurve E(A, B) mit 4 A + 27 B != 0 ist eine Kurve in der Ebene. Sie enthlt die Punkte (x y), die die Bedingung y = x + A x + B erfllen.

Instanzen der Klasse elliptic-curve speichern die Parameter a und b der Kurve und eine Instanz des Punktes in der Unendlichkeit.

Die Instanzen der Klassen point, finite-point und infinite-point reprsentieren Punkte, entweder auf der Kurve oder den unendlich fernen Punkt. Der Initialisierer fr Punkte prft, ob die Koordinaten des Punkts zur Kurve passen.

Die Methode add addiert zwei Punkte.</comment-de><comment-en></comment-en><export>elliptic-curve</export><export>get-infinite-point</export><export>point</export><export>finite-point</export><export>infinite-point</export><export>initialize</export><export>make-point</export><export>get-curve</export><export>add</export><body>#| elliptic curve |#

(defclass elliptic-curve ())

(defmethod initialize ((this elliptic-curve) (a residue-class) (b residue-class)) 
  (and
    (same-ring? a b)
    (not (zero? 
      (+ (* (new residue-class (get-ring a) 4) a a a)
        (* (new residue-class (get-ring b) 27) b b)))))
  (progn
    (.= this a a)
    (.= this b b)
    (.= this infinite-point (new infinite-point this))
    (freeze this)))

(defmethod get-infinite-point ((this elliptic-curve)) 
  t
  (. this infinite-point))

(defmethod make-point ((this elliptic-curve) (x residue-class) (y residue-class)) 
  t
  (new finite-point this x y))

(defmethod add-points ((this elliptic-curve) (x1 residue-class) (y1 residue-class) (x2 residue-class) (y2 residue-class))
  (not 
    (and 
      (= x1 x2) 
      (= y1 (- (new residue-class (get-ring y2) 0) y2))))
  (let
   ((m (if
     (= x1 x2)
     (/ (+ (* (new residue-class (get-ring x1) 3) x1 x1) (. this a)) (+ y1 y1))
     (/ (- y2 y1) (- x2 x1)))))
    (let
      ((x3 (- (* m m) x1 x2)))
      (let
        ((y3 (- (* (- x1 x3) m) y1)))
        (make-point this x3 y3)))))

#| point on elliptic curve or point at infinity |#

(deftrait point ())

(defclass finite-point (point))

(defclass infinite-point (point))

(defmethod initialize ((this finite-point) (curve elliptic-curve) (x residue-class) (y residue-class))
  (with-slots-read-only (a b) curve
    (=
      (* y y) 
      (+ (* x x x) (* a x) b)))
  (progn
    (.= this curve curve)
    (.= this x x)
    (.= this y y)
    (freeze this))))

(defmethod initialize ((this infinite-point) (curve elliptic-curve)) 
  t
  (progn
    (.= this curve curve)
    (freeze this)))

(defmethod get-curve ((this point))
  t
  (. this curve))

(defmethod same-curve? ((point-1 point) (point-2 point))
  t
  (= (get-curve point-1) (get-curve point-2)))

(defmethod add ((point-1 infinite-point) (point-2 point)) 
  (same-curve? point-1 point-2)
  point-2)

(defmethod add ((point-1 point) (point-2 infinite-point)) 
  (same-curve? point-1 point-2)
  point-1)

(defmethod add ((point-1 finite-point) (point-2 finite-point))
  (same-curve? point-1 point-2)
  (let
    ((curve (get-curve point-1))
     (x1 (. point-1 x))
     (y1 (. point-1 y))
     (x2 (. point-2 x))
     (y2 (. point-2 y)))
    (if
      (or
        (and (= x1 x2) (zero? y1) (zero? y2))
        (and (= x1 x2) (not (= y1 y2))))
      (get-infinite-point curve)
      (add-points curve x1 y1 x2 y2))))</body><dependency><name>residue-class</name><minimum-required-version>4</minimum-required-version><uri>local:residue-class</uri></dependency></module><module><name>factorize</name><version>13</version><uri>local:factorize</uri><comment-de>Das Modul faktorisiert Zahlen mit der Methode der elliptischen Kurven.</comment-de><comment-en></comment-en><export>trial-division-search-factors</export><export>elliptic-curve-search-factor</export><export>elliptic-curve-find-factor</export><export>factorize</export><body>(setq *small-primes*
  (quote 
    (2 3 5 7 11 13 17 19
     23 29 31 37 41 43 47
     53 59 61 67 71 73 79
     83 89 97)))

(defproc trial-division-search-factors (n)
  (select-if
    (lambda (p) (integer? (/ n p)))
    *small-primes*))

(defproc binary-logarithm (n)
  (if
    (&lt; n 2)
    1
    (+ 1 (binary-logarithm (floor (/ n 2))))))

(defproc newton-root (n e a)
  (let
    ((b (- a (floor (/ (- (expt a e) n) (* e (expt a (- e 1))))))))
    (if
      (= a b)
      a
      (newton-root n e b))))

(defproc non-zero-random (n)
  (+ 1 (random (- n 1))))

(defproc random-multiplier (n)
  (let
    ((lblb (binary-logarithm (binary-logarithm n))))
    (let
      ((r (newton-root n lblb 1))
       (m 1))
      (dotimes (i (* 8 lblb) m)
        (setq m (lcm m (non-zero-random r)))))))

(defproc make-random-point (n)
  (let
    ((ring (new residue-class-ring n)))
    (let
      ((a (new residue-class ring (non-zero-random n)))
       (x (new residue-class ring (non-zero-random n)))
       (y (new residue-class ring (non-zero-random n))))
      (let
        ((curve (new elliptic-curve a (- (* y y) (* x x x) (* a x)))))
        (make-point curve x y)))))

(defmethod repeated-addition (k (p finite-point) s)
  (and
    (integer? k)
    (&gt;= k 0))
  (cond
    ((= k 0) 
      s)
    ((odd? k) 
      (repeated-addition (/ (- k 1) 2) (+ p p) (+ s p)))
    (t 
      (repeated-addition (/ k 2) (+ p p) s))))

(defmethod repeated-addition (k (p infinite-point) s)
  t
  s)

(defmethod repeated-addition (k (p point))
  (and
    (integer? k)
    (&gt;= k 0))
  (repeated-addition k p (get-infinite-point (get-curve p))))

(defproc elliptic-curve-search-factor (product)
  (let
    ((multiplier (random-multiplier product))
     (curve-count 0))
    (loop
      (let
        ((point (make-random-point product)))
        (catch-and-apply
          (quote no-multiplicative-inverse)
          (lambda (name value) (return (gcd value product)))
          (repeated-addition multiplier point)))
      (setq curve-count (+ curve-count 1))
      (when (greater? curve-count 10)
        (return nil)))))

(defproc elliptic-curve-factor-generator (channel product)
  (loop
    (when (closed-channel? channel)
      (return nil))
    (awhen (elliptic-curve-search-factor product)
      (send-on-channel channel it nil)
      (return nil))))

(defproc elliptic-curve-find-factor (product)
  (let
    ((channel (make-channel 0)))
    (progn
      (dotimes (i *thread-count*)
        (go 
          (elliptic-curve-factor-generator channel product)))
      (ensure
        (receive-from-channels (list channel) nil)
        (close-channel channel)))))

(defproc factorize (number)
  (if
    (&lt; number 2)
    nil
    (if
      (prime? number)
      (list number)
      (aif
        (trial-division-search-factors number)
        (append it (factorize (/ number (apply * it))))
        (let
          ((factor (elliptic-curve-find-factor number)))
          (append
            (factorize factor)
            (factorize (/ number factor))))))))</body><dependency><name>expt</name><minimum-required-version>1</minimum-required-version><uri>local:expt</uri></dependency><dependency><name>residue-class</name><minimum-required-version>4</minimum-required-version><uri>local:residue-class</uri></dependency><dependency><name>elliptic-curve</name><minimum-required-version>0</minimum-required-version><uri>local:elliptic-curve</uri></dependency></module><module-exports></module-exports></sheet>

Credits

Andreas Motzek

16 projects • 9 followers

I like algorithms, code, statistics and decisions based on them, solving difficult problems and, if possible, avoiding them elegantly.

Have an unused Raspberry Pi or other SBC?

Things used in this project

Hardware components

Story

Is it a Cluster or is it a Grid?

Preparing the Grid Nodes

Using the Grid

Factoring Numbers

Code

distributed-factorization.sheet.xml

Credits

Andreas Motzek

Comments

Embed the widget on your own site

Have an unused Raspberry Pi or other SBC?

Have an unused Raspberry Pi or other SBC?

Things used in this project

Hardware components

Story

Is it a Cluster or is it a Grid?

Preparing the Grid Nodes

Using the Grid

Factoring Numbers

Code

distributed-factorization.sheet.xml

Credits

Andreas Motzek

Comments

Related channels and tags