<jupyter_start><jupyter_text>Tiles with Borders**Contents*** [Introduction](introduction)* [Tile Properties](Tile-Properties)* [Movement into Tiles](Movement-into-Tiles)* [Coordination](Coordination)  * [A Single, Non-distributed System](A-Single,-Non-distributed-System)  * [A Distributed System](A-Distributed-System)* [Data](Data)* [Footnotes](Footnotes) IntroductionWe're exploring tiles of width $2^n$, where $n \geqslant 1$ (since tiles of width $2^0$ are just single cells). Powers of 2 are both practical for scaling purposes as well as making the math easier.  With cells making up tiles, we'll also look at collections of tiles; these too will have widths of powers of two, namely $2^m$. We'll spend most of our time working with the case $m=2$, since that's enough tiles two explore all possible interactions. Here's a visual of $m = 0$, $m = 1$, and $m = 2$:[![Example 4x4 tiles](files/images/4x4-tile-examples-thumb.png)](files/images/4x4-tile-examples.png)The example above shows tiles with borders; furthermore, it highlights where those borders may have interaction with other tiles, and what type of interactions. In particular:* &9632; Cells with this colour are conflcit-free, contention-free zone: they will never have shared data for time steps  $t + 1$.* &9632; Cells with this colour are part of a tile's outer border. Since they are part of the outer border, with no overlap with cells of other tiles, they can only be considered temporarily conflict-free. This is due to the fact that the tiles could be moved or other tiles could be placed against their borders. As such, at every time step, we should check if a new tile has been placed adjacent; if not, we may continue to regard it as conflict-free for time steps  $t + 1$.* &9632; Dark blue cells are outer border cells of a tile that are adjacent to other tiles's outer border cells and could have shared data between two cells of two different tiles for time steps $t + 1$.* &9632; Light purple cells are non-outer border cells of two adjacent tiless' non-outer border cells and could have shared data between two cells of two different tiles for time steps $t + 1$.* &9632; Dark purple cells are non-outer border cells of four adjacent tiles' non-outer border cells and could have shared data between fours cells of four different tiles for time steps $t + 1$.The idea here is that if we split up an agent-based world into tiles, how much processing in those tiles can be done independently of the others, and how much will need to be coordinated? If a model is running across a collection of tiles and time $t_0$ is the initial state, then at $t_1$, the most any tile's agents could make it into another tile would be around the perimater of the tile to a depth of one cell. It is in this case (where agent data has moved from one tile to another) that coordination is required between the work being done on tiles; conversely,  agents who remain in a given tile don't need to have their work coordinated. Tile PropertiesIn general, each tile has the following properties:* Cell dimentions: $2^n$ by $2^n$* Total number of cells: $2^n \times 2^n$* Number of inner cells: $(2^n - 2) \times (2^n - 2)$* Number of border cells: $2^n \times 2^n - ((2^n - 2) \times (2^n - 2))$Collections of tiles follow the same rules, and as such, have the same properies:* Tile set dimentions: $2^m$ by $2^m$* Total number of tiles in a set: $2^m \times 2^m$* Number of inner tiles: $(2^m - 2) \times (2^m - 2)$* Number of border tiles: $2^m \times 2^m - ((2^m - 2) \times (2^m - 2))$We can write some functions that define these for us:<jupyter_code>to_lisp()$
;; Decided not to use this next one
;; (defun power2p (n)
;;   (if (eql 0 (and (/= n 0) (logand n (- n 1))))
;;     t
;;     nil))
    
(defun total-count (n)
  (* (expt 2 n) (expt 2 n)))
  
(defun inner-count (n)
  (* (- (expt 2 n) 2) 
     (- (expt 2 n) 2)))

;; This is less efficient than the new one, below
;; (defun border-count (n)
;;  (- (total-count n) (inner-count n)))

(defun border-count (n)
  (+ (* (- (expt 2 n) 2) 4) 4))

(defstruct props power width total-count inner-count border-count)

(defun get-props (n)
  (make-props
    :power n
    :width (expt 2 n)
    :total-count (total-count n)
    :inner-count (inner-count n)
    :border-count (border-count n)))<jupyter_output><empty_output><jupyter_text>So, for the trivial case:<jupyter_code>(get-props 0)<jupyter_output><empty_output><jupyter_text>The case of $n = 1$ isn't all that interesting from a practical perspective (since no cells are conflict free), but here are its properties:<jupyter_code>(get-props 1)<jupyter_output><empty_output><jupyter_text>And a visual for it in single tile, four-tile, and 16-tile arrangements:[![Example 2x2 tiles](files/images/2x2-tile-examples-thumb.png)](files/images/2x2-tile-examples.png)We saw above, when defining the different cell types, an example of $n=2$, but let's look again:<jupyter_code>(get-props 2)<jupyter_output><empty_output><jupyter_text>Again, the visual:[![Example 4x4 tiles](files/images/4x4-tile-examples-thumb.png)](files/images/4x4-tile-examples.png)Properties for $n = 3$:<jupyter_code>(get-props 3)<jupyter_output><empty_output><jupyter_text>And we have this set of tiles (one tile, four tiles, and 16 tiles):[![Example 8x8 tiles](files/images/8x8-tile-examples-thumb.png)](files/images/8x8-tile-examples.png)Properties for a few more, with no corresponding visuals:<jupyter_code>(get-props 4)
(get-props 5)
(get-props 6)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10839224216059452, 'fraction_numerical': 0.021388435744063804, 'mean_word_length': 4.602030456852792, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '350974', 'license': 'Apache-2.0', 'n_tokens_mistral': 1766, 'n_tokens_neox': 1651, 'n_words': 753, 'path': 'notebooks/Tiles with Borders.ipynb', 'repo_name': 'bluest-eel/research', 'size': '5517'}